「ナップサック問題」の版間の差分

2008年11月13日 (木) 13:22時点における最新版

【なっぷさっくもんだい (knapsack problem)】

重さが $a_{i}\,$ の物品 $i\,$ をナップサックに詰めるとき, 重量制限 $b\,$ の下で価値 $c_{i}\,$ の総和が最大になるものを選ぶという次の整数計画問題.

目的関数	$\sum _{i=1}^{n}c_{i}x_{i}\to \,$ 最大化
制約条件	$\sum _{i=1}^{n}a_{i}x_{i}\leq b,x_{i}\,$ ：非負整数

NP困難であるが, 実際には大規模な問題でも最適に解くことができる. 板取り問題などの部分問題などにも広く利用されている.

@@ 1行目: / 1行目: @@
-【なっぷさっくもんだい (knapsack problem)】
+'''【なっぷさっくもんだい (knapsack problem)】'''
-重さが<math>a_i\,</math>の物品<math>i\,</math>をナップサックに詰めるとき, 重量制限 <math>b\,</math> の下で価値 <math>c_i\,</math> の総和が最大になるものを選ぶという次の整数計画問題.
+重さが<math>a_i\,</math>の物品<math>i\,</math>をナップサックに詰めるとき, 重量制限 <math>b\,</math> の下で価値 <math>c_i\,</math> の総和が最大になるものを選ぶという次の整数計画問題. <br>
-\begin{center}
+<table align = center>
-\begin{tabular}{ll}
+   <tr><td>目的関数　</td> <td><math>\sum_{i=1}^{n} c_{i}x_{i} \to \,</math>最大化</td></tr>
-目的関数 & $\displaystyle{\sum_{i=1}^n \: c_ix_i }\; \to \; 最大化 $\\
+   <tr><td>制約条件　</td> <td><math>\sum_{i=1}^{n} a_{i}x_{i} \leq b,x_i\,</math>：非負整数</td></tr>
-制約条件 & $\displaystyle{\sum_{i=1}^n \: a_ix_i }\leq b,\; x_i:\;$非負整数
+</table>
-\end{tabular}
-\end{center}
 NP困難であるが, 実際には大規模な問題でも最適に解くことができる. 板取り問題などの部分問題などにも広く利用されている.
+[[Category:組合せ最適化|なっぷさっくもんだい]]
+[[category:近似・知能・感覚的手法|なっぷさっくもんだい]]
+[[Category:グラフ･ネットワーク|なっぷさっくもんだい]]