背包问题我分了一下四种
类型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#include #include #include 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[i] 要开的大一些
#include#include #include #include 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]
【相似题目】
1.
【注意：w[i]*=v[i]】
2.
（2） 类01背包不超体积
代码：
#include#include #include #include 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<
【温馨提示】
这类题目和类型一相似，但是类型一是考虑最优价值，类型二只是考虑体积
【相似题目】
1.
2.
（3） 稍复杂的01背包
代码
#include#include #include #include #include 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]
【温馨提示】
。。。一点也不复杂。。。就是把之前的 i 换成了一个数组
类型2 完全背包
代码
#include#include #include #include 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]
【温馨提示】
完全背包就是 每种物品都可以用无限次
01背包是每种物品只有一件
【相似题目】
类型3 二维背包
代码
#include#include #include #include #include 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<
【温馨提示】
二维背包限制条件双重
类型4 背包方案数
代码
#include#include #include #include #include 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<
小结
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] ] ;