ナップサック問題(knapsack problem)とは、重さと価値の決まった品物から、重さの和が上限を超えないように選んで価値の和を最大にする問題で、資源の配分や切り出しの計画に現れる。品物を分割してよいなら価値と重さの比の順に詰めれば解ける。分割できない 0-1 の問題は NP 困難であるが、重さか価値が小さい整数なら表の動的計画法で解ける。近似では、比の順の解と最大の品物のよい方が最適値の半分を保証し、価値を丸めると任意の精度の近似解が多項式時間で求まる。
ナップサック問題(knapsack problem)は、重さと価値が決まった品物から、重さの和が上限を超えないように選んで、価値の和を最大にする問題である。予算の配分、切り出しの計画、貨物の積み込みなど、1 つの資源を取り合う選択の問題の原型で、整数計画法 の資本予算のモデルの中でもっとも簡単な形である(BHM77 §9.1、pp. 273–274)。
問題の形は単純だが、計算の難しさの性質は対照的なものがそろっている。
横軸を重さの和、縦軸を価値の和として、4 個の品物の 16 通りの部分集合を点で描いた図。価値と重さの比の順に品物を足した折れ線が点の上側を通り、上限 W=10 の縦線との交点が連続緩和の値 26.2 である。0-1 の最適値は 23 である。
$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)。
$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]$ は非有界の問題の最適値である。
$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$
$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))$ 個である。
$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$ は比の順に入る限り詰めた解の価値である。
$v_{\max}:=\max_iv_i$ とする。$k$ 番目までの解と、もっとも価値の高い品物 1 個の解のよい方の価値は、$\frac12\mathrm{OPT}$ 以上である。すなわち
$$
\max\{V_k,\ v_{\max}\}\ge\frac12\mathrm{OPT}
$$
である。定数 $\frac12$ はこれ以上大きくできない。
$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)$ である。
大きさ:$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 困難な問題でも、数値の精度を落とせば易しくなるところが、この問題の特徴である。
入力の型から方法を選ぶ。
| 入力の様子 | 方法 | 根拠 |
|---|---|---|
| $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$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | |||||||||
| 1 | 0 | 3 | ||||||||
| 2 | 0 | 3 | 4 | 7 | ||||||
| 3 | 0 | 3 | 4 | 6 | 7 | 9 | 10 | 13 |
最下行で値が $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$ と逆にたどれる。
価値 $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 のあとの説明 |
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する