なっとく！アルゴリズムを読んで 実際の思考経過

セル[i][j] = 1,前の最大値（セル[ i - 1] [ j ] の値）

　　　　  2, 現在の品物の価値　＋　残りのスペースの価値

　　　　　　　　　　　　　　　　　↑セル[i - 1] [ j - 品物の重さ]

この式を、このグリッドの全てのセルで使うことができます。あなたのグリッドもこのグリッドと同じになるはずです。部分問題の解き方の説明を覚えれいるでしょうか。２つの部分問題の解を組み合わせることで、より大きな問題を解いたのです。

ナップザック問題のあれこれ

まだ魔法のような気がしているかもしれませんね。ここでは、よくある質問に応えることとします。

１,品物を追加するとどうなるか

以前は気づかなかった、４つ目の品物を盗めることに気づいたとします。iphoneも盗むことができます。

この新しい品物を考慮に入れるとしたら、最初から何もかも計算し直さなければならないのでしょうか。そんなことはありません。動的計画法が推定値に基づいて問題を徐々に解いていくことを思い出してください。これまでの最大値があります。

4ポンドのナップザックでは、3500ドル分の品物を盗むことができます。それが最終的な最大値であると考えましたが、ここでiphoneの行を追加してみましょう。

あたらしい最大値が判明します。続きを読む前に、この新しい行を埋めてみてください。最初のセルから始めましょう。このiphoneは１ポンドのナップザックに入ります。これまでの最大値は1500ドルでありましたが、iphoneには2000ドルの価値があります。代わりにiphone(I) を盗むことにしましょう。

→次のセルには、iphoneとギターが収まります。

３つ目のセルでも、iphoneとギターを盗む方が良いので、そのままにします。

最後のセルで、面白いことが起きます。現在の価値は3500ドルです。代わりにiphoneを盗むとすると、３ポンド分の空きが生じます。

　　3500(ノートPC＋ギター）VS　（2000　iphone + ？？？ 

３ポンド分の空き）

それらの３ポンドには、2000ドル分の価値があります。iphoneの2000ドルと古い部分問題による2000 ドルを足すと、4000ドルになります。これが新しい最大値です。　新しい最終グリッドは次のようになります。

ここで質問です、　列の値がそもそも「減少」することはあるのでしょうか。そのようなことはあり得るのでしょうか。

答えは、いいえです。次のセルに進むたびに現在の最大推定値を書き込んでいくのですから、最大推定値が以前よりも小さくなることはありません。