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