题目链接：https://www.acwing.com/problem/content/5/
题目描述
有 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
分析
约定
我们记第i件物品的体积，价值和数量为v[i],w[i],s[i]
状态表示
f(i,j)表示满足如下条件的方案的最大价值：
- 仅从前i件物品中选择
- 所选取的物品体积小于等于j
状态划分
对于f(i,j),存在两大种情况：
- 没选第i件物品
- 选了第i件物品，要考虑选了几件，1、2、3直到上限都应该考虑
状态转移方程
对应状态划分，我们便可以得到相应的状态转移方程：
- f(i,j)=f(i-1,j)
- f(i,j)=max(f[i-1][j-k*v[i]]+k*w[i]) (k*v[i]<=j,k<=s[i])
注意，第二行方程中的第一维为i-1，因为该种大情况将选了几件第i件物品剥离开再求和处理的。
显然，我们要取的f(i,j)应当是两大种情况的最大值，将二者形式统一，最终的状态转移方程如下：
f(i,j)=max(f(i-1,j-k*v[i])+k*w[i]) (k*v[i]<=j,k<=s[i])
总结与思考
对于多重背包问题，基本的解决思路与完全背包相同，这时我们会理所当然向着完全背包的优化思路上走，究竟行不行呢？我们来试一试。
按照完全背包的优化思路，我们寻找状态转移方程的特性：
- f(i,j)=max(f(i-1,j),f(i-1,j-v[i])+w[i],f(i-1,j-2*v[i])+2*w[i],f(i-1,j-3*v[i])+3*w[i],···,f(i-1,j-s[i]*v[i])+s[i]*w[i])
- f(i,j-v[i])=max(f(i-1,j-v[i]),f(i-1,j-2*v[i])+w[i],f(i-1,j-3*v[i])+2*w[i],···,f(i-1,j-s[i]*v[i])+s[i]*w[i],f(i-1,j-(s[i]+1)*v[i])+(s[i]+1)*w[i])
注意加粗部分，完全背包中加粗部分项数一致，每项均差w[i]，但观察上面两个式子，项数是不一致的，无法得到下面的状态转移方程：
f(i,j)=max(f(i-1,j)+f(i,j-v[i])+w[i]) (j-v[i]>=0)
因此，老的优化思路是走不通的。
二进制优化
二进制优化是多重背包的一个经典优化方法。
对于第i件物品，我们将其分组为1、2、4、8、···、2^n，最后一组如果不够2的整数次幂则直接单算一组。
易证，对于任意选择小于等于s[i]件第i件物品的方案，都可以通过上述分组的组合等价得到。
将上述每一个分组都当作一个物品，该物品体积为该组物品体技之和，价值为该组物品价值之和，这样就将多重背包问题转化为了0-1背包问题，从而将时间复杂度从NVS降低到了NVlogS(大致表示)。
朴素解法AC代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 101;
int n, V;
int v[N], w[N], s[N];
int f[N][N];
int main()
{
cin >> n >> V;
for (int i = 1; i <= n; i++)
cin >> v[i] >> w[i] >> s[i];
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= V; j++)
{
for (int 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][V] << endl;
return 0;
}
二进制优化AC代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 13000;
int n, V;
int v[N], w[N];
int f[N];
int main()
{
cin >> n >> V;
int cnt = 0;
for (int i = 1; i <= n; i++)
{
int a, b, c;
cin >> a >> b >> c;
int k = 1;
while (k <= c)
{
cnt++;
v[cnt] = k * a;
w[cnt] = k * b;
c -= k;
k *= 2;
}
if (c)
{
cnt++;
v[cnt] = c * a;
w[cnt] = c * b;
}
}
n = cnt;
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;
}