强烈安利：
背包九讲
As a 初学者，背包问题我分了一下四种
类型1 01背包问题
【温馨提示】
01 背包问题 重点理念：
f[i][v] 表示前 i 件物品（部分或全部）恰放入一个容积为 v 的背包可以获得的最大价值
转移方程为 f[i][v ]= max ( f[i-1][v] , f[i-1][v-w[i]] + c[i] )
（1）简单的01背包
代码一：
#include<iostream> #include<cstdio> #include<cmath> #include<algorithm> using namespace std; int te[10000],jia[10000],f[10000][10000]; int main() { int t,m; cin>>t>>m; for(int i=1;i<=m;i++) cin>>te[i]>>jia[i]; for(int i=1;i<=m;i++) for(int j=t;j>=0;j--) { if(te[i]<=j) f[i][j]=max(f[i-1][j],f[i-1][j-te[i]]+jia[i]); //此处max直接调用的位于《iostream》函数 else f[i][j]=f[i-1][j]; } cout<<f[m][t]; return 0; }
代码二：强行降一维，但要注意 f[i] 要开的大一些
#include<iostream> #include<cstdio> #include<cmath> #include<algorithm> using namespace std; int te[10000],jia[10000],f[1000000]; int main() { int t,m; cin>>t>>m; for(int i=1;i<=m;i++) cin>>te[i]>>jia[i]; for(int i=1;i<=m;i++) for(int j=t;j>=te[i];j--) { if(f[j]<f[j-te[i]]+jia[i]) f[j]=f[j-te[i]]+jia[i]; } cout<<f[t]; return 0; }
【相似题目】
【注意：w[i]*=v[i]】
2.P2871 [USACO07DEC]手链Charm Bracelet
（2） 类01背包不超体积
代码：
#include<iostream> #include<cstdio> #include<cmath> #include<algorithm> using namespace std; int w[1000],f[1000000]; int main() { int v,n; cin>>v>>n; for(int i=1;i<=n;i++) cin>>w[i]; for(int i=1;i<=n;i++) for(int j=v;j>=w[i];j--) { f[j]=max(f[j],f[j-w[i]]+w[i]); } cout<<v-f[v]; return 0; }
【温馨提示】
这类题目和类型一相似，但是类型一是考虑最优价值，类型二只是考虑体积
【相似题目】
1.P2639 [USACO09OCT]Bessie的体重问题Bessie
2.P2925 [USACO08DEC]干草出售Hay For
（3） 稍复杂的01背包
代码
#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<algorithm> using namespace std; int t[5000],f[5000],q[5000],p[5000]; int main() { int rqy,lao,m,n,tem,ak; cin>>rqy>>lao>>m>>n; ak=lao/rqy; for(int i=1;i<=n;i++) { cin>>t[i]; t[i]*=ak; } for(int i=1;i<=m;i++) cin>>p[i]>>q[i]; cin>>tem; for(int i=1;i<=m;i++) for(int j=tem;j>=t[p[i]];j--) { if(f[j]<f[j-t[p[i]]]+q[i]) f[j]=f[j-t[p[i]]]+q[i]; } cout<<f[tem]; return 0; }
【温馨提示】
。。。一点也不复杂。。。就是把之前的 i 换成了一个数组
类型2 完全背包
代码
#include<iostream> #include<cstdio> #include<cmath> #include<algorithm> using namespace std; int v[10000],c[10000],f[1000000]; int main() { int t,m; cin>>t>>m; for(int i=1;i<=m;i++) cin>>v[i]>>c[i]; for(int i=1;i<=m;i++) for(int j=v[i];j<=t;j++) if(f[j]<f[j-v[i]]+c[i]) f[j]=f[j-v[i]]+c[i]; cout<<f[t]; return 0; }
【温馨提示】
完全背包就是 每种物品都可以用无限次
01背包是每种物品只有一件
【相似题目】
类型3 二维背包
代码
#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<algorithm> using namespace std; int v[5000],m[5000],k[5000],f[5000][5000]; int main() { int V,M,n; cin>>V>>M>>n; for(int i=1;i<=n;i++) cin>>v[i]>>m[i]>>k[i]; for(int i=1;i<=n;i++) for(int j=V;j>=v[i];j--) for(int z=M;z>=m[i];z--) { f[j][z]=max(f[j][z],f[j-v[i]][z-m[i]]+k[i]); } cout<<f[V][M]; return 0; }
【温馨提示】
二维背包限制条件双重
【附加题目】
P1910 L国的战斗之间谍
类型4 背包方案数
代码
#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<algorithm> using namespace std; long long a[50000],f[50000]; int main() { int n,m; cin>>n>>m; f[0]=1; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n;i++) for(int j=m;j>=a[i];j--) f[j]+=f[j-a[i]]; //此处累加方案数 cout<<f[m]; return 0; }
小结
1. 01背包 一个物品只能选一次
for ( int j=n ; j>=v[i] ; j-- ) dp[ j ]=max( dp[ j ] , dp[ j - v[i] ] + w[i] ) ;
2. 完全背包 一个物品可以选无限次
for ( int j=v[i] ; j<=n ; j++) dp[ j ]=max( dp[ j ] , dp[ j - v[i] ] + w[i] ) ;
3.二维背包
dp[ j ][ z ]=max( dp[ j ][ z ] , dp[ j - v[i] ][ z - m[i] ] + k[i] ) ;
4.背包方案数
dp[ j ]+=dp[ j - a [i] ] ;