题解 | 【模板】多重背包

#include <iostream>
#include <vector>

using namespace std;

const int N = 3005;

//逻辑和完全背包基本一样，注意对于w = 0的特殊处理，然后就是使用二维状态会oom，需要使用dp[j]滚动数组优化
int main() {
	int t;
	cin >> t;
	int n, m;
	vector<int> w;
	vector<int> v;
	long long* dp = new long long[N + 1];
	while (t--) {
		cin >> n >> m;
		long long tmp_w, tmp_v, s, free_val = 0;
		w.clear();
		v.clear();
		w.push_back(-1);
		v.push_back(-1);
		for (int i = 0; i < n; i++) {
			cin >> tmp_w >> tmp_v >> s;
			//二进制拆分
			if (tmp_w) {
				int base = 1, cnt = min(m / tmp_w, s);
				while (cnt > 0) {
					int num = min(cnt, base);
					w.push_back(num * tmp_w);
					v.push_back(num * tmp_v);
					cnt -= num;
					base <<= 1;
				}
			} else {
				free_val += s * tmp_v;
			}
		}
		//0 - 1背包, 有num个物品 
		int num = w.size() - 1;
		for (int i = 0; i <= N; i++) {
			dp[i] = 0;
		}
		for (int i = 1; i <= num; i++) {
			for (int j = m; j >= w[i]; j--) {
				dp[j] = max(dp[j - w[i]] + v[i], dp[j]);
			}
		}
		cout << dp[m] + free_val << endl; 
	}
}