組み合わせ問題
提供: Internet Web School
(版間での差分)
Moderator (トーク | 投稿記録)
(ページの作成: ナップサック問題 5個の品物<math>1~5</math>があり,それぞれの重さと値段は表3の通りである.これをナップサックに詰めたいが,これに…)
次の差分→
(ページの作成: ナップサック問題 5個の品物<math>1~5</math>があり,それぞれの重さと値段は表3の通りである.これをナップサックに詰めたいが,これに…)
次の差分→
2020年11月23日 (月) 16:34時点における版
ナップサック問題
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\)を取る変数x_i を導入すると,この問題は 制約条件\(5x_1+3x_2+2x_3\ +4x_4 + 1x_5 \leq 10\) のもとに \(100x_1+200x_2+150x_3+250x_4 + 100x_5\) を最大化する問題になる.