多重背包问题与分组背包

多重背包的含义： 物品数量不再是无穷多。

看题：

思路，既然物品个数有限，但还要判断要装几个，我们可以用暴力的做法，三重循环，每层循环控制自己的变量，容易理解。第三层循环就是控制装的物品的个数，我们通过分析可以得知，在使用次数不超过物品提供个数的同时，还要小于背包的空间限制。

#include<bits/stdc++.h>using namespace std;const int N = 1010;int v[N];int w[N];int s[N];int f[N][N];//f数组放最大价值，里面的列数组存放体积Vint main(){int i,j,k,m,n;cin>>n>>m;for(i=1;i<=n;i++){scanf("%d%d%d",&v[i],&w[i],&s[i]);}for(i=1;i<=n;i++){for(j=1;j<=m;j++){for(k=0;k<=s[i]&&k*v[i]<=j;k++){//注意条件在物品个数限制内同时还要在空间限制内f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);}}}cout<<f[n][m]<<endl;return 0;}

暴力做法效率肯定不高，那就进行二进制优化 。

所谓的二进制，就是不用遍历每一个数从1~n，而是进行打包处理，在1~n之间把数变成1，2，4，8，......，。我们可以证明的是，这些二进制数可以表示从1~之间的任何整数，这样大大缩短了时间。

比如，现在给出一堆苹果和10个箱子，选出n个苹果。将这一堆苹果分别按照1,2,4,8,16,.....512分到10个箱子里，那么由于任何一个数字x ∈[1,1024]，都可以从这10个箱子里的苹果数量表示出来，但是这样选择的次数就是 ≤10次 。下面代码里第一个for循环就是做的这个工作：k=1开始，分包，k不断平方操作，包的范围不断加大，直到小于等于每种物品的个数s，该过程完成，之后把剩下的s-k个物品继续打包（这里的s-k是小于变化后的k的），最后if里面的判断就是s还有的情况下就是没正好分完，就把剩下的单独打包，完成二进制优化！

#include<bits/stdc++.h>using namespace std;const int N = 25000;int v[N];int w[N];int f[N];//f数组放最大价值，里面的列数组存放体积Vint main(){int i,j,m,n;int sum=0;cin>>n>>m;for(i=1;i<=n;i++){int a,b,s;cin>>a>>b>>s;int k=1;while(k<=s){sum++;v[sum]=a*k;w[sum]=b*k;s-=k;k*=2;}if(s>0){sum++;v[sum]=a*s;w[sum]=b*s;}}n=sum;for(i=1;i<=n;i++){for(j=m;j>=v[i];j--){f[j]=max(f[j],f[j-v[i]]+w[i]);}}cout<<f[m]<<endl;return 0;}

---------------------------------------------------------------------------------------------------------------------------------

分组背包

分组背包顾名思义就是有不同组的物品，每个组里面又有不同多的物品。

这种题型优化的地方在于组别的输入。我们可以使用一个一维数组s[i]储存不同组别的组内物品个数，用for循环数组即可使用里面的组内组数。此外，v[i][j],w[i][j],也需要用到二维数组，其中i是组别，j是组内物品的id（题目中没有我们可以自己给他编号）。

#include<bits/stdc++.h>using namespace std;const int N = 110;int v[N][N];int w[N][N];int f[N];//f数组放最大价值，里面的列数组存放体积Vint s[N];int main(){int m,n;cin>>n>>m;for(int i=0;i<n;i++){cin>>s[i];for(int j=0;j<s[i];j++){cin>>v[i][j]>>w[i][j];}}for(int i=0;i<n;i++){for(int j=m;j>=0;j--){for(int k=0;k<s[i];k++){//每个物品最多选一遍，遍历一遍即可，此处同时对应上面物品的idif(j>=v[i][k]){f[j]=max(f[j],f[j-v[i][k]]+w[i][k]);}}}}cout<<f[m]<<endl;return 0;}

这个版本是边输入边储存，计算的优化。

#include<bits/stdc++.h>using namespace std;const int N = 110;int v[N];int w[N];int f[N];//f数组放最大价值，里面的列数组存放体积Vint main(){int m,n;cin>>n>>m;for(int i=0;i<n;i++){int s;cin>>s;for(int j=0;j<s;j++)cin>>v[j]>>w[j];for(int j=m;j>=0;j--){for(int k=0;k<s;k++){if(j>=v[k]){f[j]=max(f[j],f[j-v[k]]+w[k]);}}}}cout<<f[m]<<endl;return 0;}

如果觉得《多重背包问题与分组背包》对你有帮助，请点赞、收藏，并留下你的观点哦！