01ナップサック問題を動的計画法で解く場合の考え方

重さの単位はkgで、問題の都合上整数です。 その他のツッコミどころとかはスルーでお願いします。 まずはとっかかりとなる考え方として、それぞれの品を持っていく/置いていくで場合分けをして総当りのグラフを書きましょう。 1つ目の品はカメラの三脚(3kg、7千円)です。 荷物が何もないところから始まって、三脚を持って行かない場合はそのまま、持っていく場合はその分の重さと価値を足します。 次の品物は手提げ金庫(2kg、4千円)です。 総当りということで、場合分けの数は倍々に増えていきます。 次の品物はゲーム機(2kg、8千円)です。 また前の品物の倍のノードが追加されました。 図でこれ以上描くのは面倒ですね。 面倒かどうかはさておき、2の品数乗のノードが必要になるというのは性能的に問題があります。 例題は6個なので26+25+24...程度のノードしか使いませんが、品数が100個の場合2100+.

[atSushi]

わかりやすい図解