【競技プログラミング】0-1ナップサック問題Ⅱをやってみた【組合せ最適化】 - Qiita

1.初めに ・アルゴリズムを学ぶために、競技プログラミングを始めました。 ・AOJのコースをやっていくので、その備忘録を残します。 ・前回は最長増加部分列問題を解いたので、今回は「0-1ナップサック問題Ⅱ」を解いていきます。 2.0-1ナップサック問題Ⅱ 2.1問題 価値が $v_i$ 重さが $w_i$ であるような $N$ 個の品物と、容量が $W$ のナップザックがあります。次の条件を満たすように、品物を選んでナップザックに入れます。 ・選んだ品物の価値の合計をできるだけ高くする。 ・選んだ品物の重さの総和は $W$ を超えない。 価値の合計の最大値を求めてください。 入力 １行目に２つの整数 $N$、$W$ が空白区切りで１行に与えられます。 続く $N$ 行で $i$ 番目の品物の価値 $v_i$ と重さ $w_i$ が空白区切りで与えられます。 出力 価値の合計の最大値を１行に