ナップサック問題 とは？

重さの上限を超えず、価値の合計を最大にする選び方を考える問題だよ。ここでは各品物を丸ごと入れるか入れないかを選ぶ0–1型を考える。図の重さと価値は説明用の架空の設定なんだ。

カメラ3kg・5万円、PC7kg・8万円、タブレット6kg・6万円だね。全部だと16kgで入らない。カメラとPCなら10kg・13万円、カメラとタブレットなら9kg・11万円。この例の最大はカメラとPCだよ。

n個それぞれを入れるか入れないかで、候補は2のn乗通りになる。30個なら約10億通りだね。容量や品物までの部分問題の結果を記録する動的計画法など、全部を列挙する以外の解き方があるよ。

重さと容量を整数で扱う基本的な方法の計算量はO(nW)だよ。Wは容量の数値なので、品物が少なくてもWが巨大なら重い。入力を表す桁数に対して常に多項式時間という意味ではなく、擬多項式時間と呼ぶんだ。

容量と品物ごとの重さ・価値で表せる選択なら、この形でモデル化できるよ。ただし相互依存や複数の制約などがあれば別の考慮が必要。一般の0–1型はNP困難だけれど、小さな例の最適解まで求められないという意味ではないんだ。