動的計画法(順方向)
前回は 動的計画法 を使ってナップサック問題を解きましたが、再帰関数に合わせてループの順番が 逆方向 になっていました。
今回は、このループの順番を 順方向 に変えてみます。
[ナップサック問題]
N個の品物があります。 それぞれの品物の 重さ(weight) と 価値(value) は分かっています。 これらの品物からいくつか選んでナップサックに詰めていきます。 ナップサックにい列品物の総和は capacity を超えてはいけません。 選んだ品物の価値の総和として考えられる最大値を求めて下さい。
解法・ソースコード
ループを 順方向 に変えるためには、ループ文 と 漸化式 を少し変更する必要がありますが、根本的な内容は前回記事の処理と変わりません。
[Google Colaboratory]
1 | #---------- 入力例 ---------- |
ループを 順方向 に変えることで、ループ文 や 漸化式 がシンプルで分かりやすくなったのではないでしょうか。
[実行結果]
解: 7
解(価値の総和の最大値)はこれまで同様 7 となっています。