「ナップサック問題」の版間の差分
ナビゲーションに移動
検索に移動
Albeit-Kun (トーク | 投稿記録) |
|||
| (3人の利用者による、間の3版が非表示) | |||
| 1行目: | 1行目: | ||
| − | 【なっぷさっくもんだい (knapsack problem)】 | + | '''【なっぷさっくもんだい (knapsack problem)】''' |
重さが<math>a_i\,</math>の物品<math>i\,</math>をナップサックに詰めるとき, 重量制限 <math>b\,</math> の下で価値 <math>c_i\,</math> の総和が最大になるものを選ぶという次の整数計画問題. <br> | 重さが<math>a_i\,</math>の物品<math>i\,</math>をナップサックに詰めるとき, 重量制限 <math>b\,</math> の下で価値 <math>c_i\,</math> の総和が最大になるものを選ぶという次の整数計画問題. <br> | ||
| − | <table> | + | <table align = center> |
<tr><td>目的関数 </td> <td><math>\sum_{i=1}^{n} c_{i}x_{i} \to \,</math>最大化</td></tr> | <tr><td>目的関数 </td> <td><math>\sum_{i=1}^{n} c_{i}x_{i} \to \,</math>最大化</td></tr> | ||
<tr><td>制約条件 </td> <td><math>\sum_{i=1}^{n} a_{i}x_{i} \leq b,x_i\,</math>：非負整数</td></tr> | <tr><td>制約条件 </td> <td><math>\sum_{i=1}^{n} a_{i}x_{i} \leq b,x_i\,</math>：非負整数</td></tr> | ||
</table> | </table> | ||
NP困難であるが, 実際には大規模な問題でも最適に解くことができる. 板取り問題などの部分問題などにも広く利用されている. | NP困難であるが, 実際には大規模な問題でも最適に解くことができる. 板取り問題などの部分問題などにも広く利用されている. | ||
| + | |||
| + | [[Category:組合せ最適化|なっぷさっくもんだい]] | ||
| + | |||
| + | [[category:近似・知能・感覚的手法|なっぷさっくもんだい]] | ||
| + | |||
| + | [[Category:グラフ･ネットワーク|なっぷさっくもんだい]] | ||
2008年11月13日 (木) 13:22時点における最新版
【なっぷさっくもんだい (knapsack problem)】
重さがの物品をナップサックに詰めるとき, 重量制限 の下で価値 の総和が最大になるものを選ぶという次の整数計画問題.
| 目的関数 | 最大化 |
| 制約条件 | ：非負整数 |
NP困難であるが, 実際には大規模な問題でも最適に解くことができる. 板取り問題などの部分問題などにも広く利用されている.