ナップサック問題 3 D(Beta)編（paizaランク B 相当）
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
シェア用URL:
ツイートする
問題
下記の問題をプログラミングしてみよう！
N 個の品物それぞれの重さ wi と価値 vi が与えられます。
選んだ品物の重さの総和が W を超えないように選んだ時の価値の最大値を出力してください。
問題や制約は先ほどの問題と同じですが、遷移の方法を変えて解答してみましょう。
先ほどの問題では、どの状態から dp[i][j] へ遷移するかで場合分けをしていましたが
今回は、dp[i][j] から i 番目の品物を選ぶ・選ばないといった直後の行動で場合分けして
・dp[i][j] -> dp[i+1][j] (i 番目の品物を選ばない場合)
・dp[i][j] -> dp[i+1][j+w[i]] (選ぶ場合)
といった遷移を実施しましょう。
- 入力される値
-
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
