動的計画法
今回は 動的計画法 を使ってナップサック問題を解いていきます。
動的計画法 は、値を覚えて再利用する手法です。
[問題]
N個の品物があります。 それぞれの品物の 重さ(weight) と 価値(value) は分かっています。 これらの品物からいくつか選んでナップサックに詰めていきます。 ナップサックにい列品物の総和は capacity を超えてはいけません。 選んだ品物の価値の総和として考えられる最大値を求めて下さい。
前回使った メモ化した辞書型データ に注目してみます。
メモ化した辞書型データ は、i番目以降の品物から、重さの総和がj以下 となるように選んだ時の 価値の総和の最大値 となっています。
再帰関数を書かなくても、直接この 漸化式 を用いて各項目の値を順に計算していくことにより、単純な二重ループ で ナップサック問題を解くことができます。
(漸化式 とは、数列の各項をその前の頃から1通りに定める規則を表す等式のことです。)
解法・ソースコード
前回の 再帰関数 をもとに、動的計画法 で実装を行うと下記のようになります。
2重ループの中で、漸化式 を使って順番に メモ化テーブル に結果を格納していきます。
[Google Colaboratory]
1 | #---------- 入力例 ---------- |
[実行結果]
解: 7
解(価値の総和の最大値)はこれまで同様 7 となりました。