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

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

問題

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

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

・ヒント:配列を工夫する
W の最大値が 10^9 と非常に大きいため、今までの解法では実行時間に間に合いません。
そこで、配列に入れる情報を重さの累計から別の物へ変えてみましょう。

入力される値

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

N W
w_1 v_1
w_2 v_2
...
w_N v_N

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

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

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

・入力はすべて整数
・1 ≦ N ≦ 100
・1 ≦ W ≦ 10^9
・1 ≦ w_i ≦ 10^7 (1 ≦ i ≦ N)
・1 ≦ v_i ≦ 100 (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

問題一覧へ戻る