N 個の品物があります。i 番目の品物は値段 c_i 円、価値 v_i です。予算 W 円以内で品物を選ぶとき（各品物は 0 個または 1 個だけ選べます）、選んだ品物の価値の合計をできるだけ大きくしてください。その最大値を出力してください。
入力は以下の形式で標準入力から与えられます。1 行目に品物の個数 N と予算 W、続く N 行に各品物の値段 c_i と価値 v_i が与えられます。
N W c_1 v_1 c_2 v_2 ... c_N v_N
予算 W 円以内で得られる価値の合計の最大値を半角数字で出力してください。
| 入力 | 出力 |
|---|---|
3 10 3 4 4 5 5 6 | 11 |
1 5 10 100 | 0 |
最後はアルゴリズムの花形、動的計画法（DP）の代表格「0-1 ナップサック問題」です。最初は難しく感じて当然。でも、ここを理解できると一気に世界が広がります。
考え方の核は「予算ごとに、達成できる最大価値を表にして覚えておく」こと。
dp[j] ＝「予算 j 円のときの最大価値」とする表を用意するdp[j] を更新するj を W から下げていく）。こうすると「同じ品物を 2 回入れる」ミスを防げますなぜ大きい方から回すのか、紙に小さな例で dp の変化を書いてみると「なるほど！」と腑に落ちます。DP は手を動かして表を埋めるのが一番の近道。焦らず、一歩ずつ。ここまで来たあなたなら、必ず越えられます！
下のエディタにコードを書き、「コンパイル・実行」で試し、「提出」で全テスト採点します。言語は C / C++ / Java から選べます。全テスト合格でこの問題はクリア（👑）です。
本番の編集・コンパイル・実行・採点は Exercode 上で行います。このページは予習・練習用です（実行は Wandbox の実コンパイラを利用）。