組み合わせ問題
提供: Internet Web School
(版間での差分)
| 3 行: | 3 行: | ||
5個の品物<math>1 \sim 5</math>があり,それぞれの重さと値段は表3の通りである．これをナップサックに詰めたいが, | 5個の品物<math>1 \sim 5</math>があり,それぞれの重さと値段は表3の通りである．これをナップサックに詰めたいが, | ||
これには10㎏までしか詰め込めない．値段の合計が最大となる品物選ぶにはどうすれば良いか． | これには10㎏までしか詰め込めない．値段の合計が最大となる品物選ぶにはどうすれば良いか． | ||
| + | |||
表3 | 表3 | ||
| + | |||
品物 １ ２ ３ ４ ５ | 品物 １ ２ ３ ４ ５ | ||
| 14 行: | 16 行: | ||
品物<math>i\ (i=1,2,3,4,5)</math>をナップサックに入れるか入れないかによって | 品物<math>i\ (i=1,2,3,4,5)</math>をナップサックに入れるか入れないかによって | ||
| + | |||
値<math>1,0</math>を取る変数<math>x_i</math> を導入すると,この問題は | 値<math>1,0</math>を取る変数<math>x_i</math> を導入すると,この問題は | ||
制約条件 | 制約条件 | ||
2020年11月23日 (月) 16:37時点における版
ナップサック問題
5個の品物1∼5があり,それぞれの重さと値段は表3の通りである．これをナップサックに詰めたいが, これには10㎏までしか詰め込めない．値段の合計が最大となる品物選ぶにはどうすれば良いか．
表3
品物 １ ２ ３ ４ ５
重さ ５ ３ ２ ４ １
値段 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 を最大化する問題になる.
