組み合わせ問題

提供: Internet Web School

UNIQ20cdf79830b59b1c-MathJax-2-QINU2 による版

ナップサック問題

5個の品物\(1 \sim 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\)を取る変数\(x_i\) を導入すると,この問題は  制約条件\(5x_1+3x_2+2x_3\ +4x_4 + 1x_5 \leq 10\) のもとに \(100x_1+200x_2+150x_3+250x_4 + 100x_5\) を最大化する問題になる.

個人用ツール