4549 - 分组背包Ⅱ
时间限制 : 1 秒
内存限制 : 128 MB
有许多物品,分作K组。有一个容量为C的背包。现在所有物品中，最多选择K件物品放入背包。每一个分组中，最多只能选择一件物品。放入第i件物品耗费的空间是w_i得到的价值是v_i。求解在不超过容量的前提下，将哪些物品装入背包可使价值总和最大。
输入
第一行为两个正整数N、C和K，N表示物品数量，C表示背包容量，K表示最大的组编号。
第2行至第N+1行，每行为三个正整数wi,vi,ki，表示第i个物品的重量、价值和分组。
输出
放入背包的最大价值。
以及选择的物品列表，本题包含SPJ，可以以任意顺序输出任意一种方案
样例
输入
6 10 3 2 1 1 3 3 1 4 8 2 6 9 2 2 8 3 3 9 3
输出
20 6 3 2
提示
1 \leq K \leq n \leq 1001,1 \leq C \leq 10001
来源
原创