题解 | 【模板】完全背包

#include <iostream>
#include <vector>

using namespace std;

const int N = 1005;

//一开始按照常规思路在for (j...)循环枚举一个for (k = 0; k < m / w[i]...)会超时，问ai可以使用二进制优化转换为0 - 1背包问题，注意int** dp = new int*[N * 15];是因为n <= 1000 < 2 ^ 10，所以其实new int*[N * 10]就够了
int main() {
	int t;
	cin >> t;
	int n, m;
	vector<int> w;
	vector<int> v;
	int** dp = new int*[N * 15];
	for (int i = 0; i <= N * 15; i++) {
		dp[i] = new int[N + 1]; 
	}
	while (t--) {
		cin >> n >> m;
		int tmp_w, tmp_v;
		w.clear();
		v.clear();
		w.push_back(-1);
		v.push_back(-1);
		for (int i = 0; i < n; i++) {
			cin >> tmp_w >> tmp_v;
			//二进制拆分
			int base = 1, cnt = m / tmp_w;
			while (cnt > 0) {
				int num = min(cnt, base);
				w.push_back(num * tmp_w);
				v.push_back(num * tmp_v);
				cnt -= num;
				base <<= 1;
			} 
		}
		//0 - 1背包, 有num个物品 
		int num = w.size() - 1;
		for (int i = 0; i <= num; i++) {
		 	dp[i][0] = 0;
		}
		for (int i = 0; i <= m; i++) {
			dp[0][i] = 0;
		}
		for (int i = 1; i <= num; i++) {
			for (int j = 1; j <= m; j++) {
				dp[i][j] = j >= w[i] ? max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]) : dp[i - 1][j]; 
			}
		}
		cout << dp[num][m] << endl; 
	}
}