ソースを表示

提供: Internet Web School

以下に示された理由により、このページの編集を行うことができません:

このページのソースを閲覧し、コピーすることができます:

ナップサック問題 5個の品物<math>1~5</math>があり,それぞれの重さと値段は表3の通りである．これをナップサックに詰めたいが,これには10㎏までしか詰め込めない．値段の合計が最大となる品物選ぶにはどうすれば良いか． 表3 品物 　　１ 　２ 　３ 　４ 　５ 重さ 　　５ 　３ 　２ 　４ 　１ 値段 　　250 　200 　150 　250 　100 解　法　 品物<math>i\ (i=1,2,3,4,5)</math>をナップサックに入れるか入れないかによって値<math>1,0</math>を取る変数x_i を導入すると,この問題は 　制約条件<math>5x_1+3x_2+2x_3\ +4x_4　+ 1x_5 \leq 10</math> のもとに <math>100x_1+200x_2+150x_3+250x_4　+ 100x_5</math> を最大化する問題になる.

組み合わせ問題 に戻る。