組み合わせ問題

提供: Internet Web School

(版間での差分)
1 行: 1 行:
ナップサック問題
ナップサック問題
-
5個の品物<math>1 \sim 5</math>があり,それぞれの重さと値段は表3の通りである.これをナップサックに詰めたいが,これには10㎏までしか詰め込めない.値段の合計が最大となる品物選ぶにはどうすれば良いか.
+
5個の品物<math>1 \sim 5</math>があり,それぞれの重さと値段は表3の通りである.これをナップサックに詰めたいが,
 +
これには10㎏までしか詰め込めない.値段の合計が最大となる品物選ぶにはどうすれば良いか.
表3
表3
-
品物   1  2  3  4  5 \\
+
品物   1  2  3  4  5  
-
重さ   5  3  2  4  1 \\
+
 
 +
重さ   5  3  2  4  1  
 +
 
値段   250  200  150  250  100
値段   250  200  150  250  100
 +
解 法 
解 法 
-
品物<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>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>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:36時点における版

ナップサック問題

5個の品物\(1 \sim 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\) を最大化する問題になる.

個人用ツール