組み合わせ問題

提供: Internet Web School

ナップサック問題

5個の品物\(1 \sim 5\)があり,それぞれの重さと値段は表3の通りである．これをナップサックに詰めたいが, これには10㎏までしか詰め込めない．

値段の合計が最大となる品物選ぶにはどうすれば良いか．

表3

品物 　　１ 　２ 　３ 　４ 　５

重さ 　　５ 　３ 　２ 　４ 　１

値段 　　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\)

を最大化する問題になる.