ナップサック問題

ナップサック問題#

  • 読み: なっぷさっくもんだい

  • 英名: Knapsack Problem

ナップサックの中にいくつかの品物を詰め込むことを考える. ナップサック問題は,「詰め込んだ品物の総価値を最大にするためにはどの品物を選択するとよいのか」という問題である. ただし,ナップサックと品物にはそれぞれ容量が与えられており, 詰め込む品物の総容量がナップサックの容量を超えてはいけないという条件がある. この問題は,プロジェクトの選択や物資の購入などの問題に応用されている.

なお,同じ品物を複数個詰め込むことを許す場合「整数ナップサック問題」と呼ぶ. 一方,各品物についてナップサックに詰め込むことができるのは 1 個だけという制限を加えた場合は「0-1 ナップサック問題」と呼び, 典型的な 0-1 整数計画問題として知られている.

また,それぞれ容量が異なるナップサックを複数個用意した際, 総価値が最大になるように品物を詰め込むためにはどの品物をどのナップサックに詰め込むとよいかを求める多制約ナップサック問題も研究されている.

ナップサック問題の定式化および SIMPLE での記述例に関しては「Nuorium Optimizer C++SIMPLE例題集」を参照のこと.