通天之分组背包

https://www.luogu.com.cn/problem/P1757

 1 #include <stdio.h>
 2 #include <iostream>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 int h1[1001];
 7 int h2[101];//每组物品数量
 8 int h3[101][1001];//每组中每个物品的重量
 9 int h4[101][1001];//每组中每个物品的价值
10 long dp[1001];
11 
12 long maxlong(long m, long n) {
13     if (m > n)return m;
14     else return n;
15 }
16 
17 int main() {
18     int n,m;
19     cin >> m >> n;
20 
21     int zushu = 0;
22     for (int i = 1; i <= n; i++) {
23         int l, k, x;
24         cin >> l>>k>>x;
25 
26         zushu = max(zushu, x);
27         h2[x]++;
28         h3[x][h2[x]] = l;
29         h4[x][h2[x]] = k;
30     }
31 
32     for (int i = 1; i <= zushu; i++) {
33         for (int j = m; j >= 0; j--) {
34             for (int k = 1; k <= h2[i]; k++) {
35                 if (j >= h3[i][k]) {
36                     dp[j] = maxlong(dp[j - h3[i][k]] + h4[i][k], dp[j]);
37                 }
38             }
39         }
40     }
41 
42     cout << dp[m];
43     return 0;
44 }