分组背包

题目描述:

一个旅行者有一个最多能用\( V \)公斤的背包，现在有 \( n \)件物品，它们的重量分别是 \( W_1，W_2，\dots , W_n \)，它们的价值分别为\( C_1, C_2 , \dots , C_n \)。这些物品被划分为若干组，每组中的物品互相冲突，最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

输入格式:

第一行：三个整数，\( V \) (背包容量，\( V \lt 200 \) )，\( N \) (物品数量，\( N \le 30 \) ) 和 \( T \) (最大组号，\( T \le 10 \))；

第 \( 2 \dots N+1 \) 行：每行三个整数 \( W_i,  C_i ,  P \) ，表示每个物品的重量，价值，所属组号。

输出格式:

仅一行，一个数，表示最大总价值。

样例输入:

10 6 3
2  1  1
3  3  1
4  8  2
6  9  2
2  8  3
3  9  3

样例输出:

20

提示:

存储每个组的编号，可以使用 \( vector \)。

时间限制: 1000ms
空间限制: 128MB

---