ナップサック問題
ナップサック問題（-もんだい）は、容量 C のナップサックが一つと、n 個の品物（各々、価値 pi, 容積 ci）が与えられたとき、ナップサックの容量 C を超えない範囲でいくつかの品物をナップサックに詰め、ナップサックに入れた品物の価値の和を最大化する問題。NP困難であることが知られている。
全ての品物について pi=ci が成り立つとき、部分和問題と等価であるため、この問題を含んでいる。
動的計画法を用いた擬多項式時間アルゴリズムや FPTAS の存在が知られているため、実用的には、ほぼ最適解を得ることができる。
関連項目
外部リンク
- MAXIMUM KNAPSACK [1]