Combinatorial - Knapsack Problem with Limitations

Time Limit : 1 sec, Memory Limit : 131072 KB

個数制限付きナップザック問題

価値が vi 重さが wi であるような N 種類の品物と、容量が W のナップザックがあります。

次の条件を満たすように、品物を選んでナップザックに入れます:

  • 選んだ品物の価値の合計をできるだけ高くする。
  • 選んだ品物の重さの総和は W を超えない。
  • i 番目の品物は mi 個まで選ぶことができる。

価値の合計の最大値を求めてください。

入力

N W
v1 w1 m1 
v2 w2 m2 
:
vN wN mN 

1行目に2つの整数 NW が空白区切りで1行に与えられる。

続く N 行で i 番目の品物の価値、重さ、個数の制限が空白区切りで与えられる。

出力

価値の合計の最大値を1行に出力する。

制約

  • 1 ≤ N ≤ 100
  • 1 ≤ vi ≤ 1,000
  • 1 ≤ wi ≤ 1,000
  • 1 ≤ mi ≤ 10,000
  • 1 ≤ W ≤ 10,000

入力例 1

4 8
4 3 2
2 1 1
1 2 4
3 2 2

出力例 1

12

入力例 2

2 100
1 1 100
2 1 50

出力例 2

150