【题目来源】
AcWing：5. 多重背包问题 II - AcWing题库
【题目描述】
有 \(N\) 种物品和一个容量是 \(V\) 的背包。
第 \(i\) 种物品最多有 \(s_i\) 件，每件体积是 \(v_i\)，价值是 \(w_i\)。
求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。
【输入】
第一行两个整数，\(N,V\)，用空格隔开，分别表示物品种数和背包容积。
接下来有 \(N\) 行，每行三个整数 \(v_i,w_i,s_i\)，用空格隔开，分别表示第 \(i\) 种物品的体积、价值和数量。
【输出】
输出一个整数，表示最大价值。
【输入样例】
4 5
1 2 3
2 4 1
3 4 3
4 5 2
【输出样例】
10
【解题思路】
【算法标签】
《AcWing 5 多重背包问题II》 #背包问题# #DP#
【代码详解】
#include <bits/stdc++.h>
using namespace std;
//二进制分组。1000种物品每种数量最多2000，最多11个二进制分组，1000*11
const int N=11010, V1=2010;
int n, V; //物品种类N、背包容量V
int v[N], w[N]; //物品分组后每组体积、价值，分组后组的数量
int f[V1]; //前i组物品，体积不超过j的最优解
int cnt; //将物品重新分组后心物品的下标，从1、2、...
int main()
{cin >> n >> V; //原始物品种类N、背包容量Vcnt = 0; //将物品重新分组组下标、组的数量for (int i=1; i<=n; i++) {int a, b, num; //a体积、b价值、num每种物品的数量cin >> a >> b >> num;int k = 1; //二进制拆分，物品组合成心物品含有原始物品数 kwhile (k<num) {cnt++;v[cnt] = a*k; //新物品的下标cnt，体积w[cnt] = b*k; //新物品的价值num -= k;k = k*2; //每次增长一倍k * 2}if (num>0) { //二进制拆分完之后 剩下的物品个数分为新的一组cnt++;v[cnt] = a*num; //剩下一组的体积w[cnt] = b*num; //剩下一组的价值}}n = cnt; //新物品的总数量n//二进制分组后物品（1--n）组，每组物品只有选与不选二种情况，成为0/1背包问题for (int i=1; i<=n; i++) {for (int j=V; j>=v[i]; j--) {f[j] = max(f[j], f[j-v[i]]+w[i]);}}cout << f[V] << endl;return 0;
}
【运行结果】
4 5
1 2 3
2 4 1
3 4 3
4 5 2
10