为了庆贺班级在校运动会上取得全校第一名成绩，班主任决定开一场庆功会，为此拨款购买奖品犒劳运动员。期望拨款金额能购买最大价值的奖品，可以补充他们的精力和体力。
现在便迎来了最终的部分——多重背包问题，一起看一下吧。
第一行二个数n(n<=500)，m(m<=6000)，其中n代表希望购买的奖品的种数，m表示拨款金额。
接下来n行，每行3个数，v、w、s，分别表示第I种奖品的价格、价值（价格与价值是不同的概念）和购买的数量（买0件到s件均可），其中v<=100，w<=1000，s<=10。
第一行：一个数，表示此次购买能获得的最大的价值（注意！不是价格）。
5 1000
80 20 4
40 50 9
30 50 7
40 30 6
20 20 1
1040
题目讲解：
这道题和前两道题的不同便在于这道题规定了取得的数量，那我们便可以用一个三重循环来实现多个选取，便转换为了01背包问题
代码实现：
for(int i=1;i<=n;i++){
for(int k=1;k<=num[i];k++){
for(int j=m;j>=price[i];j--){
dp[j]=max(dp[j],dp[j-price[i]]+value[i]);//保证将每种产品分成了num[i]份
}
}
}
对应的这道题还有相应的二进制转化优化：
优化的关键便在于取得的数字组合能得到1~n之间的每一个数。
题解代码：
#include<iostream>
using namespace std;
int n,m,price[505],value[505],num[505];
int dp[6005];
int val[2505],size[2505];
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d%d%d",&price[i],&value[i],&num[i]);
}
int cnt=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=num[i];j<<1){
size[cnt]=j*price[i];
val[cnt++]=j*value[i];
num[i]-=j;
}
if(num[i]>0){
val[cnt]=num[i]*value[i];
size[cnt++]=num[i]*price[i];
}
}
for(int i=0;i<cnt;i++){
for(int j=m;j>=size[i];j--){
dp[j]=max(dp[j],dp[j-size[i]]+val[i]);
}
}
printf("%d",dp[m]);
return 0;
}
题解思路：
多重背包求解的本质思想是转化为01背包，我们用一个cnt计数能够组合而成的数量，最关键的一点是要保证组合而成的新数组能够组合成1到n的每一个数，之后在采用01背包的思想来做便可以了。
原文：https://www.cnblogs.com/cxs070998/p/11371131.html