J17 例题-8 分组背包

题目描述

一个旅行者有一个最多能用 $V$ 公斤的背包，现在有 $n$ 件物品，第 $i$ 个物品的重量为 $W_i$，价值为 $C_i$。这些物品被划分为若干组，每组中的物品互相冲突，最多选一件。求将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

输入格式

第一行：三个整数，$V,N,T$，分别表示背包的容量、物品数量和最大的分组编号； 第 $2..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

样例分析

分别选了 $2,3,6$ 号物品，获得 $20$ 的价值。

数据范围

$100\%$ 的数据：$1 \le V \le 200; 1\leq N \leq 30; 1 \leq T \leq 10$。