题目描述
有N件物品和一个容量为V的背包，将所有的物品划分成若干组，每个组里面的物品最多选一件。第i件物品的重量是w[i]，价值是c[i]，属于组k[i]。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。
输入描述
第一行为N，V。
下面N行，第i行描述第i个物品的w[i]，c[i]，k[i]，用一个空格分隔。
输出描述
输出只有一个数，最大总价值。
测试用例
输入
7 9
6 6 3
5 10 3
3 5 1
9 4 4
6 1 4
8 3 5
5 2 2
输出
15
#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int>> vec[105];
int dp[1005], n, v, w, c, k, maxk = 0;
int main() {
cin >> n >> v;
for (int i = 1; i <= n; ++i)
scanf(" %d%d%d", &w, &c, &k), maxk = max(maxk, k), vec[k].emplace_back(w, c);
for (int i = 1; i <= maxk; ++i)
for (int j = v; j >= 1; --j)
for (auto& a : vec[i])
if (j >= a.first)
dp[j] = max(dp[j], dp[j - a.first] + a.second);
cout << dp[v];
}