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个物品的重量、价值和分组。

放入背包的最大价值。