背包
2025-05-03 16:43:27
发布于：上海
17阅读
0回复
0点赞
01背包：
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(j>=c[i])dp[i][j]=max(dp[i-1][j],dp[i-1][j-c[i]]+v[i]);
完全背包：
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
dp[i][j]=max(dp[i-1][j],dp[i][j-c[i]]+v[i]);
混合背包：
需要注意其状态转移方程，你在5.3并没有搞懂
注意看到状态转移方程dp[i][j]=max(dp[i-1][j]...) max中到底是dp[i-1][j]还是dp[i][j]
for(int i=1;i<=n;i++)
if(p[i]==0){
//完全
}else{
for(int k=1;k<=p[i];k++)
for(int j=1;j<=m;j++)
dp[i][j]=max(max(dp[i][j],dp[i][j]),dp[i-1][j-c[i]]+v[i]);
}
}
一定要用
二进制优化：
//拆成1，2，4，8，16...。合并成新的物品
for(int i=1;i<=n;i++){
int k=1;//当前的物品有多少个
while(k<=p[i]){
int cost=c[i]*k;
int value=v[i]*k;
if(cost>m)break;
//视作01背包处理
for(int j=1;j<=m;j++){
dp[i][j]=max(dp[i-1][j],dp[i-1][j-cost]+value);
}
p[i]-=k;
k*=2;
}
if(p[i]){
int cost=c[i]*p[i];
int value=v[i]*p[i];
if(cost>m)continue;
for(int j=1;j<=m;j++){
dp[i][j]=max(dp[i-1][j],dp[i-1][j-cost]+value);
}
}
}
分组背包：
#include<iostream>
using namespace std;
int main(){
vector<node>ve[15];
for(int i=0;i<N;i++){
int W,C,P;
cin>>W>>C>>P;
ve[P].push_back({W,C});
}
int dp[15][205];
for(int i=1;i<=T;i++){
for(int j=0;j<=V;j++){
dp[i][j]=dp[i-1][j];
for(int k=0;k<ve[i].size();k++){
if(j>=ve[i][k].v){
dp[i][j]=max(dp[i][j],dp[i-1][j-ve[i][k].w]+ve[i][k].v);
}
}
}
}
cout<<dp[T][V];
return 0;
}
这里空空如也
有帮助，赞一个