3013 - 分组背包
时间限制 : 1 秒
内存限制 : 16 MB
有许多物品,分作K组。有一个容量为C的背包。现在所有物品中，最多选择K件物品放入背包。每一个分组中，最多只能选择一件物品。放入第i件物品耗费的空间是w_i得到的价值是v_i。求解在不超过容量的前提下，将哪些物品装入背包可使价值总和最大。
输入
第一行为两个正整数N、C和K，N表示物品数量，C表示背包容量，K表示最大的组编号。
第2行至第N+1行，每行为三个正整数wi,vi,ki，表示第i个物品的重量、价值和分组。
输出
放入背包的最大价值。
样例
输入
6 10 3 2 1 1 3 3 1 4 8 2 6 9 2 2 8 3 3 9 3
输出
20
提示
对100%的数据，1<=N<=500,1<=C<=10000,1<=K<=100.
来源
动规专题