多重背包问题 I
有 N种物品和一个容量是 V 的背包。
第 i 种物品最多有 si 件，每件体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。
接下来有 N 行，每行三个整数 vi,wi,si用空格隔开，分别表示第 i 种物品的体积、价值和数量。
输出格式
输出一个整数，表示最大价值。
数据范围
0<N,V≤100
0<vi,wi,si≤100
输入样例
4 5 1 2 3 2 4 1 3 4 3 4 5 2
输出样例：
10
思路：多重背包和完全背包问题区别于物体数量上有明确的限制，暴力的做法就是，我们可以在完全背包的基础上加上一层循环 。
因为
f[j]=max(f[j],f[j-s[i]]+v[i],f[j-2*s[i]]+2*v[i],f[j-3*s[i]]+3*v[i],......,f[j-k*s[i]]+k*v[i]);
完整代码：
#include <iostream> using namespace std; const int N=110; int f[N],s[N],v[N],num[N]; int main(){ int n,m; cin>>n>>m; for(int i=1;i<=n;i++) cin>>s[i]>>v[i]>>num[i]; for(int i=1;i<=n;i++) for(int j=m;j>=s[i];j--) for(int k=0;k<=num[i]&&k*s[i]<=j;k++) { f[j]=max(f[j],f[j-k*s[i]]+k*v[i]); } cout<<f[m]; }
多重背包问题 II
有 N种物品和一个容量是 V的背包。
第 i种物品最多有 si件，每件体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。
接下来有 N 行，每行三个整数 vi,wi,si用空格隔开，分别表示第 i 种物品的体积、价值和数量。
输出格式
输出一个整数，表示最大价值。
数据范围
0<N≤1000
0<V≤2000
0<vi,wi,si≤2000
输入样例
4 5 1 2 3 2 4 1 3 4 3 4 5 2
输出样例：
10
思路：这里和第一个背包问题是一样的，区别在于数据量大了，所以暴力做法会TLE，然后可以用二进制优化方法。
其实就是将多重背包问题转换成01背包问题，可以这么想：每个物体有多个，那么我把所有拿物体的方式枚举出来添加到原来的问题组上，那么所有的物体就变成了数量唯一。
优化方法就在于不用枚举所有的方式，只要包括可以组成他所有数的“子数”（这个表达方式可能不太对），例如7，我们只需要插入1 ，2，4 就可以组成7以内的所有数，这里想一下二进制的表示方式。
完整代码：
#include <iostream> #include <vector> using namespace std; const int N=2010; int f[N]; struct Good{ int v,w; }; int main(){ int n,m,v,w,s; cin>>n>>m; vector<Good> goods; for(int i=1;i<=n;i++) { cin>>v>>w>>s; for(int j=1;j<=s;j*=2) { s-=j; goods.push_back({j*v,j*w}); } goods.push_back({s*v,s*w}); } for(auto good:goods) { for(int j=m;j>=good.v;j--) { f[j]=max(f[j],f[j-good.v]+good.w); } } cout<<f[m]; }
分组背包
有 N 组物品和一个容量是 V 的背包。
每组物品有若干个，同一组内的物品最多只能选一个。
每件物品的体积是 vij，价值是 wij，其中 i 是组号，j 是组内编号。
求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。
输出最大价值。
输入格式
第一行有两个整数 N，V用空格隔开，分别表示物品组数和背包容量。
接下来有 N 组数据：
每组数据第一行有一个整数 Si表示第 i 个物品组的物品数量；
每组数据接下来有 Si行，每行有两个整数 vij,wij用空格隔开，分别表示第 i个物品组的第 j 个物品的体积和价值；
输出格式
输出一个整数，表示最大价值。
数据范围
0<N,V≤100
0<Si≤100
0<vij,wij≤100
输入样例
3 5 2 1 2 2 4 1 3 4 1 4 5
输出样例：
8
思路：把分组背包理解成多层背包
每一个组--->>一个物体，
一个组内有多个物体--->>一个物体数量有多个
完整代码：
#include <iostream> using namespace std; const int N=110; int f[N],v[N],w[N]; int main(){ int n,m; cin>>n>>m; for(int i=0;i<n;i++) { int s; cin>>s; for(int j=1;j<=s;j++) cin>>v[j]>>w[j]; for(int j=m;j>=0;j--) { for(int k=1;k<=s;k++) { if(j>=v[k]) f[j]=max(f[j],f[j-v[k]]+w[k]); } } } cout<<f[m]; }
