多重背包

物品有数量限制

先自己想想

那根据完全背包的意思，三层循环的情况下，就是把边界条件改成 k*v[i]<=j && k<=s[i]

关键就是三重循环肯定不对，要优化

状态计算

先考虑 完全背包 的方式可以吗？

f[i][j] = max(f[i-1][j], f[i-1][j-v]+w, ... , f[i-1][j-sv]+sw)
f[i][j-v] = max(         f[i-1][j-v]  , ... , f[i-1][j-sv]+(s-1)w, f[i-1][j-(s+1)v]+sw)

由于 完全背包 是无限个，终止条件是背包装不下，所以后半截数量是对上的。但是多重背包有可能提前终止，那就会多这么一项，所以不能

二进制优化法

感觉就是用奇技淫巧把多重背包转变为 01 背包问题，类似那道 删除并获得点数 转变为 打家劫舍，将原问题的集合构造成一个新的集合

所以为什么用二进制，因为二进制是 01 的，每一位选或不选可以构造出 s[i]

因此就能把三层循环中的其中一层优化为 logN

具体如何表示

如果 s=200，那是按照惯例 200 ⇐ 255 吗？不是的，而是 200 = 127+73

这么做的原因是不想变复杂，又不是真的编码，只是想要一种方式能够刚好覆盖 0~200

$$s=\sum _{i=0}^k{2}^i+c$$

#include <iostream>
#include <algorithm>
 
const int N = 25000;  // 这里已经 N * logS 了
int v[N], w[N];
int dp[N];
 
int main() {
	cin >> n >> m;
 
	int cnt = 1;  // 我这里还是显式地强调一下从 1 开始
	for(int i = 0; i < n; ++i) {  // 这里要重新构造问题集合
		int a, b, s;  // 体积，价值，数量
		cin >> a >> b >> s;
 
		int k = 1;
		while(k <= s) {
			v[cnt] = k * a;
			w[cnt] = k * b;
			cnt ++ ;
 
			s -= k;
			k *= 2;
		}
		if(s > 0) {  // 不是刚好的数
			v[cnt] = s * a;
			w[cnt] = s * b;
			cnt ++ ;
		}
	}
 
	n = cnt;  // 将问题规模重置一下
	// 然后开始 01 背包
	for(int i = 1; i <= n; ++i) {
		for(int j = m; j >= v[i]; --j) {
			dp[j] = max(dp[j], dp[j-v[i]] + w[i]);
		}
	}
 
	cout << dp[m] << endl;
}