问题描述

给定 N 种物品 和一个容量为 V 的背包。

第 i 种物品：

• 体积为 vi
• 价值为 wi
• 最多可选 si 件

要求选择若干物品装入背包，使得：

• 物品总体积 ≤ V
• 总价值最大

输出最大价值。

输入格式

N V
v1 w1 s1
v2 w2 s2
...
vN wN sN