ナップサック問題 1 R(Beta)編（paizaランク C 相当）
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
シェア用URL:
ツイートする
問題
下記の問題をプログラミングしてみよう！
このチャプターでは、ナップサック問題を扱います。
ナップサック問題とは、重さと価値が設定された N 個の品物からいくつかを選んで品物の総価値を最大にするという問題です。
4 個の品物それぞれの重さ wi と価値 vi が与えられます。
選んだ品物の重さの総和が W を超えないように選んだ時の価値の最大値を出力してください。
- 入力される値
-
W
w_1 v_1
w_2 v_2
w_3 v_3
w_4 v_4
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
答えを 1 行で出力してください。また末尾に改行をいれ、余計な文字、空行を含んではいけません。
- 条件
-
すべてのテストケースにおいて、以下の条件をみたします。
・入力はすべて整数
・1 ≦ W ≦ 400
・1 ≦ w_i ≦ 100
・1 ≦ v_i ≦ 100
- 入力例1
-
9
6 5
3 1
4 3
2 2
- 出力例1
-
7
- 入力例2
-
18
9 6
3 2
11 7
4 3
- 出力例2
-
12
