AcWing
5. 多重背包问题II
接多重背包问题I，将每种s[i]个物品拆开，那么总物品数是s[1] + s[2] + ... + s[n]，这样就将多重背包问题转换为01背包问题。但是一个个枚举的效率太低，考虑二进制优化。
假如某个物品i有数量s[i] == 10，可以将其拆分为：1, 2, 4, 3，这样相当于对每个拆分内的元素打包，对于每个打包可以选或不选，通过合适的选择方案，总能组合出0-s[i]个物品数量，这样就将拆分枚举的时间复杂度由O(n)降低到O(logn).
#include <bits/stdc++.h>
using namespace std;
int n, m;
const int N = 1010, M = 2010;
int v[N], w[N], s[N];
int f[M];
int main(){
cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> v[i] >> w[i] >> s[i];
for(int i = 1; i <= n; i++){
for(int k = 1; k <= s[i]; k *= 2){
for(int j = m; j >= v[i] * k; j--){
f[j] = max(f[j], f[j - k * v[i]] + k * w[i]);
}
s[i] -= k;
}
if(s[i]){
for(int j = m; j >= s[i] * v[i]; j--)
f[j] = max(f[j], f[j - s[i] * v[i]] + s[i] * w[i]);
}
}
cout << f[m] << endl;
return 0;
}