题解 | 【模板】分组背包

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

const int G = 105, N = 3005, M = 3005;

int main() {
	int n, m , k;
	cin >> n >> m;
	long long* dp = new long long[m + 1];
	memset(dp, 0, sizeof(long long) * (m + 1));
	vector<vector<int> > obj_w(G + 1);
	vector<vector<int> > obj_v(G + 1);
		
	for (int i = 0; i <= G; i++) {
		obj_w[i].push_back(0);
		obj_v[i].push_back(0); 
	}
	int w, v, num, max_num = -1;
	for (int i = 0; i < n; i++) {
		cin >> w >> v >> num;
		obj_w[num].push_back(w);
		obj_v[num].push_back(v); 
		max_num = max(max_num, num);
	}
	for (int i = 1; i <= max_num; i++) {
		for (int j = m; j >= 0; j--) {
			for (int k = 0; k < obj_w[i].size(); k++) {
				if (j >= obj_w[i][k]) {
					dp[j] = max(dp[j], dp[j - obj_w[i][k]] + obj_v[i][k]);
				}
			}
		}
	}
	cout << dp[m] << endl; 
}