f440 - 10130 - SuperSale
題目描述
題目描述一個超售會，有 N 種商品，每種商品都有價格和重量。有 G 個人，每個人都有一個最大負重。目標是計算所有人可以攜帶的最大商品總價值，每種商品每人最多只能拿一個。
解題思路
這題可以看作是多重背包問題的變形。對於每個人，我們都可以視為一個容量為其負重的背包。然後，我們需要計算所有人的背包可以獲得的最大總價值。
程式碼使用動態規劃來解決這個問題。c[j] 陣列表示容量為 j 的背包可以獲得的最大價值。對於每種商品，我們從大到小遍歷背包容量，如果當前容量可以容納該商品，則更新背包的最大價值。
最後，對於每個人，我們查詢其背包容量對應的最大價值，並將所有人的價值加總，得到最終答案。
複雜度分析
- 時間複雜度: O(N * M * G)，其中 N 是商品數量，M 是最大重量，G 是人數。外層迴圈遍歷商品 (N)，中間迴圈遍歷背包容量 (M)，內層迴圈遍歷人數 (G)。
- 空間複雜度: O(M)，其中 M 是最大重量。
c陣列的大小為 M+1。
程式碼
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <stdio.h>
#include <algorithm>
using namespace std;
inline int read(){
int a(0);
char c('0');
while(c>='0'){
a=(a<<3)+(a<<1)+c-'0';
c=getchar_unlocked();
}
return a;
}
inline void write(int x) {
if(x==0)
putchar_unlocked('0');
else{
int stk[9],*ptr(&stk[0]);
while(x){*ptr=x%10;x/=10;++ptr;}
while(--ptr>=(&stk[0])){putchar_unlocked(*ptr+'0');}
}
}
int t,n,g;
struct bp{
int p,w;
};
int main(){
t=read();
while(t--){
n=read();
bp a[1001];
int ans=0,h;
for(int i=0;i<n;++i){
a[i].p=read();
a[i].w=read();
}
g=read();
int b[g],ma=0,mi=0;
for(int i=0;i<g;++i){
b[i]=read();
ma=max(b[i],ma);
}
int c[ma+1]={0};
for(int i=0;i<n;++i)
for(int j=ma-a[i].w;j>=0;--j)
if(!j||c[j])
c[j+a[i].w]=max(c[j+a[i].w],c[j]+a[i].p);
for(int i=0;i<=ma;++i){
mi=max(c[i],mi);
c[i]=mi;
}
for(int i=0;i<g;++i)
ans+=c[b[i]];
write(ans);
putchar_unlocked('\n');
}
}