ナップサック問題

ナップサック問題とは、「何個かの価値や容量、重量などがわかっている品物があります。ナップサックには容量や強度の制限があり、それを超えないように品物を詰めなくてはなりません。ナップサックに入れた品物の価値の和が最大になるようにするにはどの品物を選べばよいでしょうか」という問題です。

具体的には、泥棒に入った家に以下のようなものがあったとします。なるべくトータルの価値が大きくなるように盗みたいのですが、ナップサックには3,000しか入れられません。あなたなら、何をナップサックに入れますか？まずは、価値が一番高い金塊に目がいくと思います。しかし、金塊は重量が重いので、これを先に入れてしまうと、後に入れるものが制限されてしまいます。このように、価値が一番高いものから順に採用する方法を「どん欲法」といい、必ずしも最適化はされません。欲張りは結局は損をするということでしょうか。

https://gyazo.com/81d09fbc9c8a811f7c4e5aace410d527

商品の価値と重量

これを最適化問題として解いてみましょう。制約条件は重量の合計が3,000以下、変化させるのは採択の有無で、採用なら1、採用しなければ0です。この価値の合計を最大化する組み合わせを計算してみてください。組み合せは2の8乗＝256通りあります。これほど単純なモデルでもこれだけの計算をしてみなくてはいけないので、とても大変です。

実際に最適化ツールを使って計算してみたものが以下の表です。ナップサックに3,000しか入らないときには、「置物」と「絵画を」盗むのがよいようです。しかし、3,200入るナップサックだったとすれば、置物も絵画も採用せず、「金塊」「指輪」「ネックレス」「現金」を盗むのが、価値の最大化になるわけです。

https://gyazo.com/f2f5a7d10aa320618be2ec64fdb26f5e

重量制限と最適な組み合せ