ナップサック問題 — 知識ノート

容量の限られた袋に、価値の合計が最大になるよう品物を詰める問題。

\max \sum_{i} v_{i} x_{i} s.t. \sum_{i} w_{i} x_{i} \leq W, x_{i} \in {0,1}

弱 NP 困難#

NP 困難だが、動的計画法で $𝒪 (n W)$ 時間で解ける。

f (i, c) = \max (f (i - 1, c), f (i - 1, c - w_{i}) + v_{i})

$W$ が入力の値であって桁数ではないので、これは多項式時間ではない（ $W$ の桁数に対しては指数）。この種の問題を弱 NP 困難と呼び、 TSP のような強 NP 困難と区別する。

実用上は $W$ が小さければ厳密に解けるということで、数分割問題も同じ性質を持つ。

価値密度 $v_{i} / w_{i}$ の大きい順に詰める貪欲法は、 分割可能なナップサック（品物を切ってよい）では最適。 0-1 版では最適にならないが、良い初期解になる。

$\sum_{i} w_{i} x_{i} \leq W$ という不等式制約は、そのままではQUBOに載らない。スラック変数をビットで表して等式に直し、ペナルティ項として足すのが定石。このためビット数が増え、量子ハードウェアでは実装上の負担になる。

Hans Kellerer, Ulrich Pferschy, David Pisinger. Knapsack Problems. Springer, 2004. https://doi.org/10.1007/978-3-540-24777-7
Andrew Lucas. Ising formulations of many NP problems. Frontiers in Physics 2, 2014. https://doi.org/10.3389/fphy.2014.00005