ナップサック問題を動的計画法で解く - 具体例で学ぶ数学ナップサック問題とは ・荷物が $N$ 個ある ・各 $i$ に対して、$i$ 番目の荷物は重さが $w_i$、価値が $v_i$ ・ナップサックには合計重さ $W$ までしか荷物が入らない ・荷物をナップサックにうまく入れて、価値を最大化したい というのがナップサック問題です。 ※各荷物は「入れるか入れないかの２通り」とします。この問題設定を0-1 ナップサック問題と言います。 ナップサック問題は難しい 単純に考えると、入れる荷物の選び方を全て考えれば解けますが、荷物の選び方は全部で $2^N$ 通りあるので、総当りで解くのは厳しいです。 実際、ナップサック問題はNP困難と呼ばれる（計算量理論において）難しい問題のクラスに属していることが知られています。 動的計画法で解く（方針） $1$ 番目から $i$ 番目までの荷物のみを使って、容量 $w$ のナップサックに詰め込める価値の最大値を
