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

提供: ORWiki
ナビゲーションに移動 検索に移動
(新しいページ: '【なっぷさっくもんだい (knapsack problem)】 重さが$a_i$の物品$i$をナップサックに詰めるとき, 重量制限 $b$ の下で価値 $c_i$ の総和が...')
 
 
(4人の利用者による、間の5版が非表示)
1行目: 1行目:
【なっぷさっくもんだい (knapsack problem)】
+
'''【なっぷさっくもんだい (knapsack problem)】'''
  
重さが$a_i$の物品$i$をナップサックに詰めるとき, 重量制限 $b$ の下で価値 $c_i$ の総和が最大になるものを選ぶという次の整数計画問題.  
+
重さが<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困難であるが, 実際には大規模な問題でも最適に解くことができる. 板取り問題などの部分問題などにも広く利用されている.
 
NP困難であるが, 実際には大規模な問題でも最適に解くことができる. 板取り問題などの部分問題などにも広く利用されている.
 +
 +
[[Category:組合せ最適化|なっぷさっくもんだい]]
 +
 +
[[category:近似・知能・感覚的手法|なっぷさっくもんだい]]
 +
 +
[[Category:グラフ・ネットワーク|なっぷさっくもんだい]]

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

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

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

目的関数  最大化
制約条件  :非負整数

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