ナップザック‐もんだい【ナップザック問題】
ナップザック問題
ナップサック問題
(ナップザック問題 から転送)
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2021/05/07 02:08 UTC 版)
ナップサック問題(ナップサックもんだい、Knapsack problem)は、計算複雑性理論における計算の難しさの議論の対象となる問題の一つで、n 種類の品物(各々、価値 vi、重量 wi)が与えられたとき、重量の合計が W を超えない範囲で品物のいくつかをナップサックに入れて、その入れた品物の価値の合計を最大化するには入れる品物の組み合わせをどのように選べばよいか」という整数計画問題である。同じ種類の品物を1つまでしか入れられない場合(xi ∊ {0, 1})や、同じ品物をいくつでも入れてよい場合(xi は0以上の整数)など、いくつかのバリエーションが存在する。
- 1 ナップサック問題とは
- 2 ナップサック問題の概要
- 3 関連項目
- ナップザック問題のページへのリンク