AcWing 5. 多重背包问题 II【二进制优化版本】
1、与朴素版本的区别
区别在于数据范围变大了：现在是三个循环数据上限分别是(1000)(物品种数),(2000)(背包容积),第(i)种物品的体积、价值和数量的上限也是(2000),原来的每个数字上限都是(100)！
三重循环的话，计算次数就是 (1000 * 2000 * 2000=4000000000=4 * 1e9 =40)亿次
(C++)一秒可以算(1e8)次，就是(1)亿次，(40)亿肯定会超时!
2、二进制优化
朴素多重背包做法的本质：将有数量限制的相同物品看成多个不同的(0-1)背包。
优化的思路：比如我们从一个货车搬百事可乐的易拉罐（因为我爱喝不健康的快乐水~），如果存在(200)个易拉罐，小超市本次要的数量为一个小于(200)的数字(n),搬的策略是什么呢？
A、一个一个搬，直到(n)为止。
B、在出厂前打成(64)个一箱，(32)个一箱，(16)个一箱，(8)个一箱，(4)个一箱，(2)个一箱，(1)个一箱，最后剩下的打成(73)个一箱。
为什么要把剩下的(73)个打成一个包呢？不是再分解成(64),(32)这样的组合呢？这是因为我们其实本质是化解为(01)背包，一来这么分解速度最快，二来可以表示原来数量的任何子集，这样就(OK)了！
3、C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 12010, M = 2010;
int n, m;
int v[N], w[N];
int f[M];
//多重背包的二进制优化
int main() {
//优化输入
ios::sync_with_stdio(false);
cin >> n >> m;
int cnt = 0;
for (int i = 1; i <= n; i++) {
//每行三个整数 a,b,s，用空格隔开，分别表示第 i 种物品的体积、价值和数量
int a, b, s;
cin >> a >> b >> s;
//二进制优化,能打包则打包之，1,2,4,8,16,...
int k = 1;
while (k <= s) {
cnt++;
v[cnt] = a * k;
w[cnt] = b * k;
s -= k;
k *= 2;
}
//剩下的
if (s > 0) {
cnt++;
v[cnt] = a * s;
w[cnt] = b * s;
}
}
n = cnt;//数量减少啦
//01背包
for (int i = 1; i <= n; i++)
for (int j = m; j >= v[i]; j--)
f[j] = max(f[j], f[j - v[i]] + w[i]);
cout << f[m] << endl;
return 0;
}