感谢赵宗昌老师
01背包
//01 暴力 void dfs(int i,int j,int s){//对物品i进行决策，j为剩余背包重量 if(i==n+1){ ans=max(ans,s); return; } dfs(i+1,j,s);//不选 if(j>=w[i]) dfs(i+1,j-w[i],s+c[i]);//能装下就选物品i } int main(){ ... dfs(1,m,0); ... } //01 二进制枚举 int k=1<<n; for(int i=0;i<k;i++){ int W=0,C=0; for(int j=0;j<n;j++) if(i&(1<<j)){ W+=w[j+1]; C+=c[j+1]; } if(W<=m) ans=max(ans,C); } cout<<ans<<endl; //O(2^n) 适合n<=20 //01-1 for(int i=1;i<=n;i++)//前i个物品用了j的容量 for(int j=0;j<=m;j++) f[i][j]=f[i-1][j]; if(j>w[i]) f[i][j]=max(f[i][j],f[i-1][j-w[i]+c[i]); //01-2 for(int i=1;i<=n;i++) for(int j=0;j<=m;j++) for(int k=0;k<=1;k++) if(j>k*w[i]) f[i][j]=max(f[i][j],f[i-1][j-w[i]*k]+k*c[i]); //01-3滚动数组 for(int i=1;i<=n;i++) for(int j=m;>=w[i];j--)//防止一个物品选多次 f[j]=max(f[j],f[j-w[i]]+c[i]); cout<<f[m]<<endl;
完全背包
//完全-1 for(int i=1;i<=n;i++) for(int j=0;i<=m;j++){ f[i][j]=f[i-1][j]; if(j>=w[i]) f[i][j]=max(f[i][j],f[i][j-w[i]]+c[i]); } //完全-2 for(int i=1;i<=n;i++) for(int j=0;j<=m;j++) for(int k=0;k<=j/w[i];k++) f[i][j]=max(f[i][j],f[i-1][j-k*w[i]]+k*c[i]); //完全-3 for(int i=1;i<=n;i++) for(int j=w[i];j<=m;j++) f[j]=max(f[j],f[j-w[i]+c[i]);
完全背包问题转化为01背包问题来解。
最简单的想法是，考虑到第i种物品最多选V/w[i]件，于是可以把第i种物品转化为V/w[i]件费用及价值均不变的物
品，然后求解这个01背包问题。这样完全没有改进基本思路的时间复杂度，但这毕竟给了我们将完全背包问题转化
为01背包问题的思路：将一种物品拆成多件物品。
高效的转化方法是：把第i种物品拆成费用为w[i]*2^k、价值为c[i]*2^k的若干件物品，其中k满足w[i]*2^k<V。这
是二进制的思想，因为不管最优策略选几件第i种物品，总可以表示成若干个2^k件物品的和。这样把每种物品拆成
O(log(V/w[i])+1)件物品，是一个很大的改进。后面多重背包也用到这种方法。
多重背包
//多重背包-1 ->完全背包 //O(V*Σs[i]) for(int i=1;i<=n;i++) for(int j=0;j<=v;j++) for(int k=0;k<=s[i];k++) if(j>=k*w[i]) f[i][j]=max(f[i][j],f[i-1][j-k*w[i]]+k*c[i]); //滚动数组 for(int i=1;i<=n;i++) for(int j=v;j>=0;j--) for(int k=0;k<=s[i];k++) if(j>=k*w[i]) f[j]=max(f[j],f[j-k*w[i]]+k*c[i]); //多重背包-2 ->01背包+滚动数组 //第i件物品，看做s[i]件一样的物品i，变成了s[1]+..+s[n]件物品的0-1背包，每个背包取还是不取 //O(V*Σs[i]) for(int i=1;i<=n;i++) for(int j=1;j<=s[i];j++) for(int k=v;k>=w[i];k--) f[k]=max(f[k],f[k-j*w[i]]+j*c[i]); //二进制 //O(V*sum(log(s[i]))) for(int i=1;i<=n;i++){ int x,y,z,k; cin>>x>>y>>z; for(k=1;z>0;k=2*k){ int d=min(k,z); if(d>0){ w[++sn]=d*x; c[sn]=d*y; } z=z-k; } } for(int i=1;i<=sn;i++) for(int j=v;j>=w[i];j--) f[j]=max(f[j], f[j-w[i]]+c[i]);
混合背包一般完全背包单独求解，多重背包和01背包用01背包求解