二进制优化法
本质: 将多重背包转化为 01背包问题
思路:
暴力法其实相当于把多重背包中的每个物品分成 \(s\) 个物品，所以才需要那么久的时间复杂度，所以现在想一下有没有什么分法，可以通过选这些物品，选几个来表示选 \(s\) 个的所有可能。
这时候就想到了二进制，因为任何实数都可以由二进制数组成。
那么我们就可以把一个物品拆成 \(2^0，2^1，2^2，...，2^k ，(x-2^{k+1} + 1)(k为最大的2^k不大于x的实数)\)，\(\log x\) 个物品。
这些物品可以通过组合，组成 \(0-x\) 内的整数（不能漏不能多）
证明：
设一个实数为 \(x\) ，拆分成 \(2^0,2^1,2^2,...,2^k,c\) ，（ \(k\) 为最大的 \(2^k\) 不大于 \(x\) 的实数），因为 \(k\) 是最大的 \(2^k\) 不大于 \(x\) 的实数，所以可以知道 \(c < 2 ^{k + 1}\) 。
根据二进制可知 \(0\) 到 \((2^{k + 1} - 1)\) 都可以用以上的数组成
上式子 + \(c\) 可得 \(c\) 到 \((2^{k + 1} - 1 + c)\) 也都可以用以上数组成。因为 \(2^{k + 1}-1+c\) 为可以凑到的最大值，所以$ 2^{k + 1} - 1 + c = S \Rightarrow c = S - (2^{k + 1} - 1)$
现在已知 \(0 -( 2^{k + 1} - 1)\) 和 \(c - S\) 两端都可以由以上数拼接起来，现在的问题就是，这两段合在一起的时候，中间有无空缺。
如果有空缺的话，\(c > 2 ^{k + 1} - 1\) 即， \(c \ge 2^{k + 1}\)。
显然与开始得到的 \(c < 2 ^{k + 1}\) 相矛盾，可得 \(0-S\) 中的任何一个数都可以拼接起来。
时间复杂度: \(O(物品数*背包的体积*log选法) = O(N*V*logS)\)
这个时间复杂度可以过这个多重背包:5. 多重背包问题 II - AcWing题库
实现:
#include <bits/stdc++.h>
using namespace std;
const int N = 2e3 + 5;
int f[N], n, m;
struct Good
{
int w, v;
} good[N];
int main()
{
scanf("%d%d", &n, &m);
// 遍历物品
while (n--)
{
int v, w, s;
scanf("%d%d%d", &v, &w, &s);
// 记录分成多少块
int cnt = 1;
for (int i = 1; i <= s; i *= 2)
{
// 分成2^k次方的时候
// 新物品的体积和价值 = 选的个数 *单个的体积和价格
good[cnt].v = i * v;
good[cnt++].w = i * w;
s -= i;
}
// 最后一个物品
if (s > 0)
{
good[cnt].v = s * v;
good[cnt++].w = s * w;
}
// 现在相当于变成了01背包
// 遍历物品
for (int i = 1; i < cnt; i++)
// 遍历体积，由于滚动了一维，所以一定要逆序遍历
for (int j = m; j >= good[i].v; j--)
f[j] = max(f[j], f[j - good[i].v] + good[i].w);
}
printf("%d\n", f[m]);
return 0;
}