組み合わせ問題
提供: Internet Web School
UNIQ19c1ba596fd6b333-MathJax-2-QINU2 による版
ナップサック問題
5個の品物UNIQ7104b0ca30366ca5-MathJax-9-QINUがあり,それぞれの重さと値段は表3の通りである.これをナップサックに詰めたいが, これには10㎏までしか詰め込めない.
値段の合計が最大となる品物選ぶにはどうすれば良いか.
品物 | 1 | 2 | 3 | 4 | 5 |
重さ | 5 | 3 | 2 | 4 | 1 |
値段 | 250 | 200 | 150 | 250 | 100 |
品物UNIQ7104b0ca30366ca5-MathJax-10-QINUをナップサックに入れるか入れないかによって
値UNIQ7104b0ca30366ca5-MathJax-11-QINUを取る変数UNIQ7104b0ca30366ca5-MathJax-12-QINU を導入すると,この問題は
制約条件
UNIQ7104b0ca30366ca5-MathJax-13-QINU
のもとに
UNIQ7104b0ca30366ca5-MathJax-14-QINU
を最大化する問題になる. この問題はナップザック問題と呼ばれる組み合わせ最適化問題に属する.
ファイル:ナップザック.pdfにMicrosoft Excelの ソルバーを用いた解法例を示す.
作成したデータは以下の通りである.
ソルバーのパラメータ 入力は以下の通りである.
ソルバーによる結果は以下の通りである.
品物2,3,4,5 を詰め込んだときに値段の合計の最大値 700になる.