ナップサック問題 2 R(Beta)編（paizaランク B 相当）

問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！

問題

下記の問題をプログラミングしてみよう！

N 個の品物それぞれの重さ wi と価値 vi が与えられます。
選んだ品物の重さの総和が W を超えないように選んだ時の価値の最大値を出力してください。

・ヒント:状態の遷移
dp[i][j]へどの状態から遷移するかで場合分けを行い

・dp[i-1][j] -> dp[i][j] (i番目の品物を選ばない場合)
・dp[i-1][j-w[i]] -> dp[i][j] (選ぶ場合)

といった遷移を実施しましょう。

入力される値

1 行目に整数の個数を表す整数 N と整数 W が与えられ、続く N 行にそれぞれの品物の重さと価値が与えられる。

N W
w_1 v_1
w_2 v_2
...
w_N v_N

入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。標準入力からの値取得方法はこちらをご確認ください

期待する出力: 答えを 1 行で出力してください。また末尾に改行をいれ、余計な文字、空行を含んではいけません。

条件: すべてのテストケースにおいて、以下の条件をみたします。

・入力はすべて整数
・1 ≦ N ≦ 100
・1 ≦ W ≦ 100,000
・1 ≦ w_i ≦ 1,000 (1 ≦ i ≦ N)
・1 ≦ v_i ≦ 1,000 (1 ≦ i ≦ N)

入力例1: 4 18
9 6
3 2
11 7
4 3

出力例1: 12

入力例2: 5 17
5 4
7 6
2 1
4 3
13 9

出力例2: 13

問題一覧へ戻る