完全 & 多重背包
2026-06-05 20:26:41
发布于：上海
35阅读
0回复
0点赞
每日挂同学（1/1）@78鼠鼠 @156****6690@仰天长啸你爹驾到@AC酱
完全：
for(int i=1;i<=n;i++){
for(int j=1;j<=c;j++){
if(j<w[i])dp[i][j]=dp[i-1][j];
else dp[i][j]=max(dp[i-1][j],dp[i][j-w[i]]+v[i]);
}
}
P1616 一眼 ___ ___
namespace HQ{
#define int long long
void init(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
void Main(){
init();
int n,c;
cin>>c>>n;
int v[1100],w[1100];
for(int i=1;i<=n;i++){
cin>>w[i]>>v[i];
}int dp[1100][1100];
for(int i=1;i<=n;i++){
for(int j=1;j<=c;j++){
if(j<w[i])dp[i][j]=dp[i-1][j];
else dp[i][j]=max(dp[i-1][j],dp[i][j-w[i]]+v[i]);
}
}cout<<dp[n][c];
return;
}
}
省空间复杂度
for(int i=1;i<=n;i++){
for(int j=1;j<=c/w[i];j++){
for(int k=c;k>=w[i];k--){
dp[k]=max(dp[k],dp[k-w[i]]+v[i]);
}
}
}
多重背包就是多个 01 背包而已
多重：
for(int i=1;i<=n;i++){
int wi,vi,si;
cin>>wi>>vi>>si;
for(int j=1;j<=si;j++){
cnt++;
w[cnt]=wi,v[cnt]=vi;
}
}for(int i=1;i<=cnt;i++){
for(int j=c;j>=w[i];j--){
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
}
}
省时间复杂度
int cnt=0;
for(int i=1;i<=n;i++){
int wi,vi,k;
cin>>wi>>vi>>k;
for(int j=1;j<=k;j*=2){
w[++cnt]=j*wi;
v[cnt]=j*vi;
k-=j;
}if(k){
w[++cnt]=k*wi;
v[cnt]=k*vi;
}
}for(int i=1;i<=cnt;i++){
for(int j=c;j>=w[i];j--){
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
}
}
有帮助，赞一个