用的是分组背包常规做法

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int m, n;
	cin >> m >> n; // n items m total weight
	int dp[10005];
	int w[2005], v[2005], b[2005] = {};
	int t[2005][2005];
	int tn = 0;
	for(int i = 1; i <= n; i ++)
	{
		int x;
        cin >> w[i] >> v[i] >> x;
        tn = max(tn, x);
        b[x] ++;
        t[x][b[x]] = i;
    }
	for (int k = 1; k <= tn; k++)
		for (int i = m; i >= 0; i--)
			for (int j = 1; j <= b[k]; j++)
				if (i >= w[t[k][j]])
					dp[i] = max(dp[i], dp[i - w[t[k][j]]] + v[t[k][j]]);
	cout << dp[m];
	return 0;
}

 

条好必关