AcWing 5. 多重背包问题 II

题面：
有 \(N\) 件物品和一个容量是 \(V\) 的背包。
第 \(i\) 件物品最多有 \(s_i\) 件，每件体积是 \(v_i\)，价值是 \(w_i\)。
求解将哪些物品装入背包，可使这些物品的体积总和不超过背包容量，且价值总和最大。
输出最大价值。

原题链接：5. 多重背包问题 II - AcWing

先前的思路^[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];
}