https://www.luogu.com.cn/problem/P1757
# 通天之分组背包

题目背景

直达通天路·小 A 历险记第二篇

题目描述

自 $01$ 背包问世之后，小 A 对此深感兴趣。一天，小 A 去远游，却发现他的背包不同于 $01$ 背包，他的物品大致可分为 $k$ 组，每组中的物品相互冲突，现在，他想知道最大的利用价值是多少。

输入格式

两个数 $m,n$，表示一共有 $n$ 件物品，总重量为 $m$。

接下来 $n$ 行，每行 $3$ 个数 $a_i,b_i,c_i$，表示物品的重量，利用价值，所属组数。

输出格式

一个数，最大的利用价值。

样例 #1

样例输入 #1

45 3
10 10 1
10 5 1
50 400 2

样例输出 #1

10

提示

$0 \leq m \leq 1000$，$1 \leq n \leq 1000$，$1\leq k\leq 100$，$a_i, b_i, c_i$ 在 int 范围内。

const int N = 5e5 + 10;
int  dp[1010][1010];
int w[1010], v[1010], t[1010];
int g[1010][1010];
void solve()
{
    int m, n;
    cin >> m >> n;
    int h = 0;
    map<int, int> p;
    for (int i = 1; i <= n; i++)
    {
        cin >> w[i] >> v[i] >> t[i];
        p[t[i]]++;//求这个组的物品数
        h = max(h, t[i]);//求最大组数
        g[t[i]][p[t[i]]] = i;//g[i][j]代表第i组第j个物品
    }
    for (int i = 1; i <= h; i++)
    {
        for (int j = m; j >= 0; j--)
        {
            dp[i][j] = dp[i - 1][j];
            for (int k = 1; k <= p[i]; k++)
            {
                if (j >= w[g[i][k]]) dp[i][j] = max(dp[i][j], dp[i - 1][j - w[g[i][k]]] + v[g[i][k]]);
            }
        }
    }
    cout << dp[h][m] << '\n';
}