ナップサック問題

同義語:ナップザック問題knapsack problem

概要

ナップサック問題(knapsack problem)とは、重さと価値の決まった品物から、重さの和が上限を超えないように選んで価値の和を最大にする問題で、資源の配分や切り出しの計画に現れる。品物を分割してよいなら価値と重さの比の順に詰めれば解ける。分割できない 0-1 の問題は NP 困難であるが、重さか価値が小さい整数なら表の動的計画法で解ける。近似では、比の順の解と最大の品物のよい方が最適値の半分を保証し、価値を丸めると任意の精度の近似解が多項式時間で求まる。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 線形計画法, 動的計画法, NP完全

ナップサック問題(knapsack problem)は、重さと価値が決まった品物から、重さの和が上限を超えないように選んで、価値の和を最大にする問題である。予算の配分、切り出しの計画、貨物の積み込みなど、1 つの資源を取り合う選択の問題の原型で、整数計画法 の資本予算のモデルの中でもっとも簡単な形である(BHM77 §9.1、pp. 273–274)。
問題の形は単純だが、計算の難しさの性質は対照的なものがそろっている。

  • 品物を分割してよいなら、価値と重さの比の順に詰めるだけで解ける(thm-ks-fractional)。分割できないと、この方法は正しい答えを出さない。
  • 重さが整数なら、表を使う 動的計画法 で $O(nW)$ の手間で解ける(公式の表)が、これは入力の長さの多項式ではない。実際、問題は NP 困難である(thm-ks-hard)。
  • それでも、近似なら話は別である。入らない品物を除けば、比の順の解と最大の品物のよい方は最適値の半分以上を保証し(thm-ks-half)、価値を丸めて動的計画法を使うと、任意の精度の近似解が多項式時間で求まる(thm-ks-fptas)。
    再帰式の正しさの一般論は 動的計画法 にあり、そこでの 0-1 の再帰式の導出と例はこの記事では繰り返さない。分枝限定法は 整数計画法 で扱う。
    横軸を重さの和、縦軸を価値の和として、4 個の品物の 16 通りの部分集合を点で描いた図。価値と重さの比の順に品物を足した折れ線が点の上側を通り、上限 W=10 の縦線との交点が連続緩和の値 26.2 である。0-1 の最適値は 23 である。 横軸を重さの和、縦軸を価値の和として、4 個の品物の 16 通りの部分集合を点で描いた図。価値と重さの比の順に品物を足した折れ線が点の上側を通り、上限 W=10 の縦線との交点が連続緩和の値 26.2 である。0-1 の最適値は 23 である。
    図の品物は ex-ks-fractional のもので、折れ線と縦線の交点が thm-ks-fractional の値である。

定義と使える条件

ナップサック問題

$n$ 個の品物について、重さ $w_i>0$ と 価値 $v_i\ge0$ が与えられ、上限 $W\ge0$ が与えられているとする。$\{1,\dots,n\}$ の部分集合 $S$ で $\sum_{i\in S}w_i\le W$ を満たすものの中で、$\sum_{i\in S}v_i$ を最大にする問題を 0-1 ナップサック問題 という。変数 $x_i\in\{0,1\}$ で書けば
$$ \max\ \sum_{i=1}^nv_ix_i\quad\text{subject to}\quad\sum_{i=1}^nw_ix_i\le W,\quad x_i\in\{0,1\} $$
である。最適値を $\mathrm{OPT}$ と書く。単に「ナップサック問題」といえばこの問題を指すことが多い。

条件 $x_i\in\{0,1\}$ を取り替えると、次の変種になる。

変種変数の条件意味
0-1$x_i\in\{0,1\}$各品物は 1 個
有界$x_i\in\{0,1,\dots,m_i\}$各品物は $m_i$ 個まで
非有界$x_i\in\{0,1,2,\dots\}$各品物はいくつでも
分数(連続緩和)$0\le x_i\le1$品物を分割してよい
部分和0-1 で $v_i=w_i$和がちょうど上限になる選び方があるか

判定問題 は、さらに整数 $K$ が与えられ、価値の和が $K$ 以上で重さの和が $W$ 以下の $S$ があるかを問う。
この記事の結果が使える条件は次のとおりである。
(i) 入力の型:動的計画法の表の添字にする量は 0 以上の整数である(重さの表なら $w_i,W$、価値の表なら $v_i$)。
(ii) 入らない品物を除く:$w_i>W$ の品物は使えないので、はじめに除く。以下の近似の定理はこれを仮定する。
(iii) 入力の長さ:手間は入力を 2 進で書いた長さで測る。$W$ の長さは $\log_2W$ 程度である。数を 1 進で書いたときの入力の長さの多項式で抑えられる手間を 擬多項式時間 という(WS11 定義 3.2、p. 67)。動的計画法の $O(nW)$ はその例で、$W$ に比例するので、2 進で書いた入力の長さの多項式ではない。

公式の表

$V:=\sum_iv_i$ とする。手間は算術演算の回数である。

問題再帰式手間条件根拠
0-1(重さの表)$K(i,c)=\max\{K(i-1,c),\ K(i-1,c-w_i)+v_i\}$$O(nW)$$w_i,W$ が整数動的計画法 の公式の表
0-1(価値の表)$A(i,u)=\min\{A(i-1,u),\ A(i-1,u-v_i)+w_i\}$$O(nV)$$v_i$ が整数prop-ks-value-table
非有界$U(c)=\max\bigl(\{0\}\cup\{U(c-w_i)+v_i:w_i\le c\}\bigr)$$O(nW)$$w_i,W$ が整数prop-ks-one-row
有界0-1 に直す。品物 $i$ を $O(\log(m_i+1))$ 個に分ける$O\bigl(W\sum_i\log(m_i+1)\bigr)$$w_i,W$ が整数prop-ks-binary-split
部分和$T(i,t)=T(i-1,t)\vee T(i-1,t-w_i)$$O(nW)$$w_i,W$ が整数Eri19 §3.8、pp. 116–117
分数比の順に詰める$O(n\log n)$$w_i>0$thm-ks-fractional
0-1(半分ずつの全列挙)再帰式なし。rem-ks-meet$O(n2^{n/2})$なしrem-ks-meet

再帰式の値の範囲は、重さの表で $0\le c\le W$、価値の表で $0\le u\le V$ である。添字が負になる項は除く。基底は $K(0,c)=0$、$A(0,0)=0$、$A(0,u)=+\infty$($u>0$)である。

目標方法保証手間根拠
上界分数の問題の最適値 $z_{\mathrm{LP}}$$\mathrm{OPT}\le z_{\mathrm{LP}}$$O(n\log n)$thm-ks-fractional
$\frac12$ 近似比の順の解と最大の品物のよい方価値 $\ge\frac12\mathrm{OPT}$$O(n\log n)$thm-ks-half
$(1-\varepsilon)$ 近似価値を丸めて価値の表価値 $\ge(1-\varepsilon)\mathrm{OPT}$$O(n^3/\varepsilon)$thm-ks-fptas

主定理と証明

分割してよい場合

$w_i>0$ とし、品物を $v_1/w_1\ge v_2/w_2\ge\dots\ge v_n/w_n$ の順に並べる。$W_k:=w_1+\dots+w_k$、$V_k:=v_1+\dots+v_k$ とおき、$W_k\le W$ となる最大の $k$ をとる($k=0$ もありうる)。

比の順に詰める解の最適性

$k=n$ なら $x^*=(1,\dots,1)$ が分数の問題の最適解である。$k< n$ なら
$$ x_i^*=\begin{cases}1&(i\le k)\\[2pt](W-W_k)/w_{k+1}&(i=k+1)\\[2pt]0&(i>k+1)\end{cases} $$
が最適解で、最適値は $z_{\mathrm{LP}}=V_k+\dfrac{W-W_k}{w_{k+1}}v_{k+1}$ である。どちらの場合も、小数の値をとる品物は 1 個以下である。

比を重みにして上から押さえる

$k=n$ なら $x^*$ はすべての変数を上限にしているので最適である。$k< n$ とする。$0\le x_{k+1}^*< 1$ で、$x^*$ は実行可能で $\sum_iw_ix_i^*=W$ である。$\lambda:=v_{k+1}/w_{k+1}\ge0$ とおく。並べ方から、$i\le k$ で $v_i-\lambda w_i\ge0$、$i>k+1$ で $v_i-\lambda w_i\le0$、$i=k+1$ で $v_i-\lambda w_i=0$ である。
任意の実行可能な $x$ について、$\sum_iw_ix_i\le W$ と $0\le x_i\le1$ から
$$ \sum_iv_ix_i=\lambda\sum_iw_ix_i+\sum_i(v_i-\lambda w_i)x_i\le\lambda W+\sum_{i\le k}(v_i-\lambda w_i) $$
である。$x=x^*$ では、$\sum_iw_ix_i^*=W$ で、$i\le k$ で $x_i^*=1$、$i>k+1$ で $x_i^*=0$ なので、すべての不等号が等号になる。よって $x^*$ は最適である。$\square$

この $\lambda$ は 線形計画法 の双対変数にあたる。「重さ 1 あたりの値段」を $\lambda$ と決めると、値段より得な品物を全部入れ、損な品物を入れないのが最適である。
0-1 の問題の実行可能解は分数の問題の実行可能解でもあるので、$\mathrm{OPT}\le z_{\mathrm{LP}}$ である。この上界は分枝限定法の限定に使える。

価値の表

重さの表は、重さが小さい整数のときに使う。価値が小さい整数のときは、添字を価値にする。

価値の表

$v_i$ を $0$ 以上の整数とする。$\{1,\dots,i\}$ の部分集合で価値の和がちょうど $u$ であるものの、重さの和の最小値を $A(i,u)$ とする(なければ $+\infty$)。このとき公式の表の再帰式が成り立ち、$\mathrm{OPT}=\max\{u:A(n,u)\le W\}$ である。

$\{1,\dots,i\}$ の部分集合で価値の和が $u$ のものは、$i$ を含まないか、含むかである。含まないものは $\{1,\dots,i-1\}$ の部分集合で価値の和が $u$ のものである。含むものは、$i$ を除くと $\{1,\dots,i-1\}$ の部分集合で価値の和が $u-v_i$ のものになり、重さの和は $w_i$ だけ減る。この対応は全単射である。最小値をとると再帰式を得る($v_i>u$ なら後の項はない)。実行可能な $S$ の価値の和を $u$ とすると $A(n,u)\le W$ であり、逆に $A(n,u)\le W$ なら価値の和が $u$ の実行可能な $S$ がある。最適値の式はここから従う。$\square$

$w_i$ は実数でよい。この表は thm-ks-fptas の道具になる。解の復元は、右下から $A(i,u)\ne A(i-1,u)$ なら品物 $i$ を選んで $u$ を $v_i$ だけ減らす、という手順である。
同じ考え方で、組 (重さの和, 価値の和) のうち、ほかの組に支配されないものだけをリストに残す方法もある。重さと価値が整数なら、リストの長さは $W+1$ 以下、$V+1$ 以下なので、手間は $O(n\min\{W,V\})$ である(WS11 定理 3.1、p. 66 とその直後の評価、p. 67)。

1 行の表と非有界・有界の場合

1 行の更新の向き

$w_i,W$ を整数とし、長さ $W+1$ の配列 $T$ を $0$ で初期化する。$i=1,\dots,n$ の順に、$c\ge w_i$ について $T[c]\leftarrow\max\{T[c],\ T[c-w_i]+v_i\}$ と更新する。
(1) $c$ を減る順に更新すると、$T[W]$ は 0-1 の問題の最適値である。
(2) $c$ を増える順に更新すると、$T[W]$ は非有界の問題の最適値である。

右辺の $T[c-w_i]$ がいつの値か

$i$ 個の品物を使う問題の、上限 $c$ の最適値を $K(i,c)$(0-1)、$U_i(c)$(非有界)とする。
(1) $c$ が減る順なら、$T[c]$ を更新するとき $T[c-w_i]$ はまだ更新されていない。$i-1$ 回目までが終わった $T$ が $K(i-1,\cdot)$ なら、更新の式は公式の表の再帰式そのものなので、$i$ 回目のあとの $T$ は $K(i,\cdot)$ である。
(2) 非有界の問題の解は、品物 $i$ を使わないか、1 個以上使うかである。使わない解の最大は $U_{i-1}(c)$ で、使う解は 1 個取り除くと上限 $c-w_i$ の解になる。よって $U_i(c)=\max\{U_{i-1}(c),\ U_i(c-w_i)+v_i\}$ である。$c$ が増える順なら、$T[c]$ を更新するとき $T[c-w_i]$ はすでに $U_i(c-w_i)$ である。$w_i>0$ なので添字は減る。したがって $i$ 回目のあとの $T$ は $U_i(\cdot)$ である。$\square$

  1. の結果は、公式の表の 1 行の再帰式 $U(c)$ を $c$ の増える順に解いたものと同じである。1 行の表では解の復元に使う情報が残らないので、復元が要るなら、各 $(i,c)$ で更新したかどうかの 1 ビットを残す。これで記憶は $O(nW)$ ビットになる。
2 進の分割

$m\ge1$ を整数とし、$2^r-1\le m< 2^{r+1}-1$ となる $r\ge1$ をとる。$t:=m-(2^r-1)$ とおく。$1,2,4,\dots,2^{r-1},t$ の部分和の全体は $\{0,1,\dots,m\}$ である。

$1,2,\dots,2^{r-1}$ の部分和の全体は、2 進表記により $\{0,1,\dots,2^r-1\}$ である。$t$ を加えた和の全体は $\{t,t+1,\dots,m\}$ である。$t\le2^r$ なので 2 つの区間は隙間なくつながり、和集合は $\{0,\dots,m\}$ である。$\square$

有界の問題の品物 $i$($m_i$ 個まで)を、重さ・価値がそれぞれ $s$ 倍の品物の束($s=1,2,\dots,2^{r-1},t$)に置き換える($t=0$ の束は作らない)。この命題により、束の選び方が使う個数 $0,\dots,m_i$ をちょうど実現するので、0-1 の問題に直る。束は品物あたり $O(\log(m_i+1))$ 個である。

NP 困難性

判定問題の難しさ
  1. $w_i,v_i,W$ が整数のとき、0-1 ナップサック問題の判定問題は NP に属する。以下、この節では入力を整数とする。
  2. 分割問題(正の整数 $a_1,\dots,a_n$ を和の等しい 2 組に分けられるか)は、判定問題へ多項式時間で帰着する。
  3. したがって判定問題は NP 完全で、最適値を求める問題は NP 困難である。
分割問題を重さと価値の等しい場合に写す
  1. $S$ そのものが証拠である。与えられた $S$ について、重さの和と価値の和を計算して比べるのは多項式時間でできる。
  2. $a_1,\dots,a_n$ の和を $2B$ とする(和が奇数なら答えは「いいえ」で、答えが「いいえ」の入力を出力する)。$v_i=w_i=a_i$、$W=K=B$ とする。$\sum_{i\in S}a_i\le B$ かつ $\sum_{i\in S}a_i\ge B$ は、$\sum_{i\in S}a_i=B$、すなわち $S$ とその補集合の和が等しいことと同値である。変換は多項式時間でできる。
  3. 分割問題は NP 完全である(WS11 付録 B、p. 459。この記事では証明しない)。(1)(2) から判定問題は NP 完全である(NP完全)。最適値を求められれば判定問題は $K$ と比べるだけで解けるので、最適値を求める問題は NP 困難である(WS11 付録 B、pp. 459–460)。$\square$

$O(nW)$ の表があってもこれは $\mathrm{P}=\mathrm{NP}$ を意味しない。(2) の帰着で $W$ は $a_i$ の和の半分で、2 進で書くと短くても値は指数的に大きくなりうるからである。このように、NP 完全であって、数を 1 進で書けば多項式時間で解ける問題を 弱 NP 完全 という(WS11 定義 B.8、p. 459)。

近似

以下、$w_i\le W$(条件 (ii))とする。$k$ を thm-ks-fractional の前の記号とする。$V_k$ は比の順に入る限り詰めた解の価値である。

$\tfrac12$ 近似

$v_{\max}:=\max_iv_i$ とする。$k$ 番目までの解と、もっとも価値の高い品物 1 個の解のよい方の価値は、$\frac12\mathrm{OPT}$ 以上である。すなわち
$$ \max\{V_k,\ v_{\max}\}\ge\frac12\mathrm{OPT} $$
である。定数 $\frac12$ はこれ以上大きくできない。

連続緩和の値を 2 つに分ける

$k=n$ なら $V_n$ は全部の品物の価値で、$V_k\ge\mathrm{OPT}$ である。$k< n$ とする。thm-ks-fractional と $W-W_k< w_{k+1}$ から
$$ \mathrm{OPT}\le z_{\mathrm{LP}}\le V_k+v_{k+1}\le V_k+v_{\max}\le2\max\{V_k,\ v_{\max}\} $$
である。$w_{k+1}\le W$ なので品物 $k+1$ だけの解も実行可能で、$v_{\max}$ の解はどの場合も実行可能である。
定数の最良性:$m\ge3$ とし、$(v,w)$ が $(2,1),(m,m),(m,m)$ の 3 個の品物と $W=2m$ を考える。比は $2,1,1$ で、$k=2$、$V_k=m+2$、$v_{\max}=m$ である。一方 $\mathrm{OPT}=2m$ なので、比 $(m+2)/(2m)$ は $m\to\infty$ で $\frac12$ に近づく。$\square$

価値を丸める近似

$v_i$ を正の数、$0< \varepsilon< 1$ とする。$M:=v_{\max}$、$\mu:=\varepsilon M/n$、$v_i':=\lfloor v_i/\mu\rfloor$ とおく。品物の価値を $v_i'$ に替えた問題の最適解 $S$ を prop-ks-value-table の表で求めると、
$$ \sum_{i\in S}v_i\ge(1-\varepsilon)\mathrm{OPT} $$
であり、表の大きさは $O(n^3/\varepsilon)$ である。

丸めの誤差は品物 1 個あたり $\mu$ 以下

大きさ:$v_i'\le M/\mu=n/\varepsilon$ なので $V':=\sum_iv_i'\le n^2/\varepsilon$ で、表のマスの数は $(n+1)(V'+1)$、すなわち $O(n^3/\varepsilon)$ である(prop-ks-value-table。重さは実数でよい)。
精度:$O$ をもとの問題の最適解とする。丸めの定義から $\mu v_i'\le v_i< \mu(v_i'+1)$ なので、$\mu v_i'>v_i-\mu$ である。$S$ は丸めた問題の最適解で、$O$ も実行可能なので
$$ \sum_{i\in S}v_i\ge\mu\sum_{i\in S}v_i'\ge\mu\sum_{i\in O}v_i'\ge\sum_{i\in O}v_i-\lvert O\rvert\mu\ge\mathrm{OPT}-n\mu=\mathrm{OPT}-\varepsilon M $$
である。条件 (ii) により品物 1 個だけの解は実行可能なので $M\le\mathrm{OPT}$ である。よって右辺は $(1-\varepsilon)\mathrm{OPT}$ 以上である。$\square$

各 $\varepsilon>0$ について(最大化の問題なら)価値 $(1-\varepsilon)\mathrm{OPT}$ 以上の解を返し、手間が入力の長さと $1/\varepsilon$ の多項式で抑えられる方法の族を 完全多項式時間近似スキーム(FPTAS)という(WS11 定義 3.3、定義 3.4、p. 67)。この定理は WS11 定理 3.5(p. 68)で、同書によれば方法は Ibarra と Kim による(p. 78)。NP 困難な問題でも、数値の精度を落とせば易しくなるところが、この問題の特徴である。

計算の手順

入力の型から方法を選ぶ。

  1. 前処理:$w_i>W$ の品物と $v_i=0$ の品物を除く。すべて入るなら終わる。
  2. 比の順の解を作る:thm-ks-fractional で $z_{\mathrm{LP}}$ を計算し、thm-ks-half で下界を得る。上界と下界の差が十分小さければ止めてよい。
  3. 厳密解が要るなら表を選ぶ:下の表のとおり。
  4. 解を復元する:重さの表なら $K(i,c)\ne K(i-1,c)$ のとき品物 $i$ を選ぶ。価値の表は prop-ks-value-table のあとの手順である。
  5. 答えを確かめる:重さの和が $W$ 以下であることと、価値の和が表の値に等しいことを確かめる。
    入力の様子方法根拠
    $w_i,W$ が小さい整数重さの表動的計画法 の公式の表
    $v_i$ が小さい整数価値の表prop-ks-value-table
    どちらも大きいが $n$ が小さい($n\le40$ 程度)半分ずつの全列挙rem-ks-meet
    どちらも大きく $n$ も大きい連続緩和の上界による分枝限定法整数計画法 の定理「分枝限定法の正しさ」
    誤差を許す価値を丸めるthm-ks-fptas
半分ずつの全列挙

品物を半分ずつ $L,R$ に分ける。$L$ の $2^{n/2}$ 個の部分集合を重さで整列し、各位置に「そこまでの重さで達する価値の最大値」を前もって計算する。$R$ の部分集合ごとに、残りの重さで入る $L$ の部分集合のうち価値が最大のものを二分探索で求める。全部の部分集合の組を調べたのと同じになり、手間は $O(n2^{n/2})$、記憶は $O(2^{n/2})$ である。入力の数の大きさによらない。

例題

分割できる場合とできない場合

価値 $9,10,12,14$、重さ $3,4,5,7$、$W=10$ の品物を考える。比は $3,\ 2.5,\ 2.4,\ 2$ の順に並んでいる。
使う公式:thm-ks-fractional、thm-ks-half。
答え:$k=2$、$V_2=19$ で、$z_{\mathrm{LP}}=19+\frac35\cdot12=26.2$ である。比の順の解は品物 1, 2 で価値 $19$、最大の品物は $14$ で、よい方は $19$ である。0-1 の最適値は $\mathrm{OPT}=23$(品物 1, 4)なので、$19\ge\frac12\cdot23$ と $23\le26.2$ が確かめられる。比の順に詰めた解は最適でない。

価値の表

価値 $2,3,4$、重さ $3,4,6$、$W=7$ の品物を考える。
使う公式:prop-ks-value-table。
答え:$\mathrm{OPT}=5$ で、品物 1, 2 を選ぶ(重さの和 $7$)。

表を開く

各マスは $A(i,u)$ である。空欄は $+\infty$ である。

$i\backslash u$0123456789
00
103
20347
30346791013

最下行で値が $7$ 以下である最大の $u$ は $5$ である。$A(3,5)=A(2,5)$ なので品物 3 は選ばない。$A(2,5)\ne A(1,5)$ なので品物 2 を選び、$u=2$ に進む。$A(1,2)\ne A(0,2)$ なので品物 1 を選ぶ。

非有界の問題

重さ $3,5,7$、価値 $4,7,10$、$W=14$ で、各品物をいくつでも使えるとする。
使う公式:prop-ks-one-row の (2)。
答え:最適値は $20$ である(重さ 7 の品物を 2 個)。各品物 1 個までの 0-1 の問題の最適値は $17$ である。

表を開く

$c=0,\dots,14$ の $U(c)$ は $0,0,0,4,4,7,8,10,11,12,14,15,17,18,20$ である。$U(14)=U(7)+10$、$U(7)=U(0)+10$ と逆にたどれる。

個数の上限 13 の品物

価値 $5$・重さ $2$ を $13$ 個、価値 $9$・重さ $3$ を $3$ 個、価値 $4$・重さ $1$ を $2$ 個とし、$W=20$ とする。
使う公式:prop-ks-binary-split。
答え:最適値は $56$ で、たとえば使う個数を順に $5,3,1$ とすればよい($6,2,2$ でも同じ値になる)。

途中の計算を開く

$13$ は $r=3$、$t=13-7=6$ なので束 $1,2,4,6$ に分ける。$3$ は $r=2$、$t=0$ で束 $1,2$、$2$ は $r=1$、$t=1$ で束 $1,1$ である。品物は 8 個の 0-1 の問題になり、重さの表の値は $56$ である。手で確かめる。比の高い順に、重さ 1 の品物 2 個と重さ 3 の品物 3 個を入れると重さ $11$、価値 $35$ である。残りの重さ $9$ に重さ 2 の品物を 4 個入れると重さ $19$、価値 $55$ である。ここから重さ 1 の品物を 1 個減らして重さ 2 の品物を 1 個増やすと、重さ $20$、価値 $56$ となり、価値は表の値に等しい。

丸めの計算

価値 $1010,1290,1870,2340$、重さ $3,4,5,7$、$W=10$、$\varepsilon=\frac14$ とする。
使う公式:thm-ks-fptas。
答え:$\mu=146.25$、丸めた価値は $6,8,12,16$ で和は $42$ である。もとの価値の和 $6510$ に比べて表が小さい。丸めた問題の最適解は品物 1, 4 で、もとの価値は $3350$ である。これは保証の下界 $\frac34\mathrm{OPT}=2512.5$ を超え、この例では $\mathrm{OPT}=3350$ に一致する。

使える条件と反例

外す条件反例成り立たなくなること
thm-ks-fractional の分割できることex-ks-fractional の品物比の順に詰める解が 0-1 の最適解でない
thm-ks-fractional の制約が 1 本制約 $2x_1+x_2\le2$、$x_1+2x_2\le2$ で $x_1+x_2$ を最大化小数の品物が 2 個になる
thm-ks-half の最大の品物との比較$(v,w)=(2,1),(M,M)$、$W=M$比の順の解だけでは比が $2/M$ まで落ちる
thm-ks-fptas の条件 (ii)$(v,w)=(1000,100),(9,1),(1,1)$、$W=1$、$\varepsilon=\frac12$$M\le\mathrm{OPT}$ が成り立たず、丸めで価値の差が消える
丸めるのは価値(重さではない)$W=6$ で、重さ $3,4$ を偶数へ切り捨て、重さ $3,3$ を偶数へ切り上げ実行不可能な解を返すか、最適解を失う
prop-ks-one-row の更新の向き重さ $1$、価値 $1$ の品物 1 個、$W=2$ で増える順0-1 の問題の答えとして $2$ を返す
表の反例の確かめ

制約が 2 本:2 つの制約を足すと $3(x_1+x_2)\le4$ なので、最大値は $\frac43$ で、達するのは $x=(\frac23,\frac23)$ だけである($x_1+x_2=\frac43$ なら 2 つの制約はどちらも等式)。制約が 1 本のときの「小数は 1 個以下」は成り立たない。
最大の品物:比は $2,1$ なので、比の順に詰めると品物 1 が入り、残りの重さ $M-1$ に品物 2 は入らない。価値は $2$ だが $\mathrm{OPT}=M$ である。
条件 (ii):入らない品物の価値 $1000$ が $M$ になる。$\mu=\frac{1000}6\approx166.67$ で丸めた価値は $6,0,0$ である。入る品物の丸めた価値はどちらも $0$ なので、丸めた問題では空集合も最適解になり、$\mathrm{OPT}=9$ に対して価値 $0$ を返しうる。
重さの丸め:重さ $3,4$ で $W=6$ なら 2 個は同時に入らない。偶数へ切り捨てると $2,4$ で同時に入る解が現れるが、もとの問題では実行不可能である。重さ $3,3$、$W=6$ なら 2 個入るが、偶数へ切り上げると $4,4$ で 1 個しか入らず、最適解を失う。thm-ks-fptas の丸めは目的関数だけを変えるので、実行可能解の集合が変わらない。
更新の向き:$T[1]=1$ のあと $T[2]=T[1]+1=2$ となり、同じ品物を 2 度使っている。

よくある誤り

誤り正しくはなぜ
$O(nW)$ を多項式時間と言う擬多項式時間。$W$ の長さは $\log_2W$ 程度条件 (iii)、thm-ks-hard のあとの説明
比の順に詰めれば 0-1 でも最適と考える分数の場合だけ最適。0-1 では上界にしかならないex-ks-fractional
比の順の解を単独で近似解として使う最大の品物と比べるex-ks-counterexamples の最大の品物
重さが実数の問題に重さの表を使う価値の表か支配のリストを使う条件 (i)
価値の表で $A(n,u)$ の最後の $u$ を答えとする$A(n,u)\le W$ となる最大の $u$ を答えとするprop-ks-value-table
1 行の表のあとで解を復元しようとする更新の 1 ビットを残すprop-ks-one-row のあとの説明

補足

  • 切り出し問題:幅 $W$ の原反を幅 $w_i$ の製品に切る問題では、線形計画の新しい切り方の探索が、双対変数を価値とする非有界ナップサック問題になる(Lee21 §7.3、pp. 82–84)。大きな線形計画の部分問題としてこの問題が現れる例である。
  • 多次元:制約が 2 本以上の問題でも、重さの表は上限の積の大きさで作れるが、thm-ks-fractional の比の順の方法は使えない。
  • 部分和の表:$v_i=w_i$ の場合、表の値は真偽値でよく、Eri19 §3.8(p. 117)が述べるとおり $W$ が $2^n$ より十分大きければ、全列挙より遅くなる。
  • 整数計画法の中で:整数計画の問題のいくつかはこの問題と同値に直せ、この問題の解法は一般の整数計画の解法の動機になった(BHM77 p. 274)。

関連項目

参考文献

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する