ナップザック問題

数理計画分野では有名な「ナップサック問題（Knapsack problem）」を例に挙げて説明をしてみましょう。ナップサック問題とは、「何個かの価値や容量、重量などがわかっている品物があります。ナップサックには容量や強度の制限があり、それを超えないように品物を詰めなくてはなりません。ナップサックに入れた品物の価値の和が最大になるようにするにはどの品物を選べばよいでしょうか」という問題です。

https://gyazo.com/0b1a2559b0f3ac778e04a4c486d01881

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

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

https://gyazo.com/b5b94b4ab8e7be2c34a07de3c8602ccc