組み合わせ問題
提供: Internet Web School
UNIQ1f7d6e5d501b0663-MathJax-2-QINU2 による版
ナップサック問題
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 を最大化する問題になる.