题面：
有 \(N\) 件物品和一个容量是 \(V\) 的背包。
第 \(i\) 件物品最多有 \(s_i\) 件，每件体积是 \(v_i\)，价值是 \(w_i\)。
求解将哪些物品装入背包，可使这些物品的体积总和不超过背包容量，且价值总和最大。
输出最大价值。
先前的思路[1]：将 \(s\) 个物品分成 \(s\) 份
由此转换为 \(s\) 个 01背包问题，例如 7 就可以拆解为 1 1 1 1 1 1 1。
二进制优化思路：将 \(s\) 个物品分成 \(log(s)\) 份
\(2^0+2^1+2^2=1+2+4=7\)
实际上，就像每一个小于等于 7 的数都可以通过 1 2 4 这三个数字组合出来一样，
最少需要 \(ceil(\log_{2}{s})\) 个数，就可以组合出 \(0 \sim s\) 之间的所有数。
对于 \(s\) 不属于 \(2^n-1\) 的情况，将 \(s-\sum_{i=0}^{[\log_{2}{s}]} 2^i\) 作为第 \(ceil(\log_{2}{s})\) 个数即可。
例如，对于 \(10\)，就可以拆解为1 2 4 3。既然每一个 \(0\sim 7\) 之间的数都可以通过 1 2 4 组合出来，那么它们加上 \(3\) 就可以表示 \(0\sim 10\) 之间的数。
时间复杂度：\(O(n^3)\) → \(O(n^2logn)\)
#include <bits/stdc++.h>
using namespace std;
const int N = 2010;
int n, m, f[N];
struct good {
int v, w;
};
int main()
{
vector<good> goods;
cin >> n >> m;
//拆堆
for (int i = 0; i < n; i++) {
int v, w, s;
cin >> v >> w >> s;
for (int j = 1; j <= s; j *= 2) {
s -= j;
goods.push_back({ v * j, w * j });
}
if (s > 0) goods.push_back({ v * s, w * s });
}
//01板子
for (auto g : goods)
for (int j = m; j >= g.v; j--)
f[j] = max(f[j], f[j - g.v] + g.w);
cout << f[m];
}