組み合わせ問題
提供: Internet Web School
(版間での差分)
29 行: | 29 行: | ||
<math>100x_1+200x_2+150x_3+250x_4 + 100x_5</math> | <math>100x_1+200x_2+150x_3+250x_4 + 100x_5</math> | ||
- | を最大化する問題になる.[[ファイル:ナップザック.pdf]] | + | を最大化する問題になる.[[ファイル:ナップザック.pdf]]にMicrosoft Excelの ソルバーを用いた解法例を示す. |
2020年11月23日 (月) 16:47時点における版
ナップサック問題
5個の品物1∼5があり,それぞれの重さと値段は表3の通りである.これをナップサックに詰めたいが, これには10㎏までしか詰め込めない.
値段の合計が最大となる品物選ぶにはどうすれば良いか.
表3
品物 1 2 3 4 5
重さ 5 3 2 4 1
値段 250 200 150 250 100
解 法
品物i (i=1,2,3,4,5)をナップサックに入れるか入れないかによって
値1,0を取る変数xi を導入すると,この問題は
制約条件
5x1+3x2+2x3 +4x4 +1x5≤10
のもとに
100x1+200x2+150x3+250x4 +100x5
を最大化する問題になる.ファイル:ナップザック.pdfにMicrosoft Excelの ソルバーを用いた解法例を示す.