ナップサック問題
計算複雑性理論や動的計画法の例としてまず挙げられることの多い有名問題。
- 代表的な問題例
- $N$ 個の品物がある
- $i$ 番目の品物の重さは $w_i$、価値は $v_i$
- 重さの合計が $W$ を超えない範囲で、できるだけ価値を高くしてナップサックに詰めたい
- 詰められる最大価値はいくつか？
重さあたりの価値が大きい方から貪欲に詰めたくなるが、厳密に答えを出そうと思うと全て試す以外に有効な方法は見つかっていない。
「貪欲だと大きなデッドスペースができてしまうが、多少“重さ当たりの価値”が小さくても、よりデッドスペースを少なくできる組合せがあって、それが最適」になったりするので。
しかし、全て試すにも上手い方法がある。
解法
愚直全探索
全ての選ぶ/選ばないの組み合わせを試す。
$N$ 種類について選ぶ/選ばないの $2^N$ 通りを全て試せば、重さが $W$ に収まっている中で一番価値の高いものがわかる。
$2^N$ 通りにつき $N$ 個の品物の選ぶ/選ばないを調べていくので、計算量は $O(N2^N)$。
よほど $N$ が小さくない限り相当な時間がかかる。
または、既に求めた答えを記録していけば、
- $\{1,2,4,5\}$ を選んだ答えは、$\{1,2,4\}$ の答えに $5$ を追加したもの
といえるので、bitフラグなどで管理して小さい組み合わせから求めることで計算量は $O(2^N)$ となる。
動的計画法
制約によって、2通りの実装方針がある。
- 考慮する重さの上限 $W$ が小さい → キーを重さ、値を最大価値としたDP
- 考慮する価値の上限 $\sum v_i$ が小さい → キーを価値、値を最小重さとしたDP
なんとなく重さをキーとする方針の方が、問題文の意図をそのまま実装している気がしてわかりやすい。
重さの上限が小さい
- $DP[i][j]=i$ 個目の品物まで入れるか入れないか決めて、重さの総和が $j$ になる組み合わせでの最大価値
$i$ の小さい方から1つ1つ、入れるか入れないか決めていく。
最終的に一番価値の高い組み合わせを求めたいので、 途中の結果でも「偶然同じ重さになる組み合わせがあったら、その中で一番価値の高い組み合わせだけ残せばよい」。
W=15 i 1 2 3 4 w 5 3 8 2 v 1 6 9 5
3番目までを入れるか入れないか決めて、
- $i=1,2$ のみを選ぶと、重さ $8$、価値 $7$
- $i=3$ のみを選ぶと、重さ $8$、価値 $9$
なので、この場合「重さが $8$ になる中では、価値 $9$ が最大」という結果だけ覚えておけばよい。
「$1,2$ 番目を使って $3$ 番目を使わない」という組み合わせは、以降の $i=4,5,...$ の使う/使わないをどのように決めても最大になることはなく、覚えておく必要も無い。（1,2をやめて3を追加すれば必ず価値が高くなる）
これを $j=0～W$ のそれぞれについても覚えておく。すると以降は、その情報だけを元に順次更新できる。
i=1 まで
暫定重さ合計 0 1 2 3 4 5
達成できる最大価値 0 - - - - 1
i=2 まで
暫定重さ合計 0 1 2 3 4 5 6 7 8
達成できる最大価値 0 - - 6 - 1 - - 7
i=3 まで
暫定重さ合計 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
達成できる最大価値 0 - - 6 - 1 - - 9 - - 15 - 10 - -
i=4
w=2, v=5
・i=3 までの結果を 2→ ずらして +5 したものが、4番目の品物を選んだ場合の各重さに対する最大価値
・i=3 までの結果そのものが、4番目の品物を選ばなかった場合の各重さに対する最大価値
・上記2つを、重さが被る場合は最大値をとって、合成すればよい。
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
選んだ場合 - - 5 - - 11 - 6 - - 14 - - 20 - 15
選ばなかった場合 0 - - 6 - 1 - - 9 - - 15 - 10 - -
------------------------------------------------
達成できる最大価値 0 - 5 6 - 11 - 6 9 - 14 15 - 20 - 15
計算量は $O(NW)$
価値の上限が小さい
- $DP[i][j]=i$ 個目の品物まで入れるか入れないか決めて、価値の総和が $j$ になる組み合わせでの最小重さ
さっきと同様、$i$ の小さい方から1つ1つ、入れるか入れないか決めていく。
同じ価値になる組み合わせがあったら、その中で一番、重さが軽い組み合わせだけ残せばよい。
重さが軽い方が、後に続く品物をよりたくさん入れられて、どんな場合でも絶対に損しない。
計算量は価値の合計を $V$ として、$O(NV)$
実装時のワンポイント・注意点
更新の順序
実装には以下のような2次元配列を用意して埋めていくこともできるが
- $DP[i][j]=i$ 番目の品物まで入れるか入れないか決めて、合計重さが $j$ の場合の最大価値（重さをキーとする場合）
実際は、$DP[i]$ を更新するときは $DP[i-1]$ の情報しか要らないので、 $j$ のみの1次元配列を更新していった方がメモリの節約・高速化になる。
- $DP[j]=$ 合計重さが $j$ の場合の最大価値。$i$ が進む毎に中身は更新されていく
その際、$j$ を小さい方から更新していくと、誤った答えとなる。
i 1 2 3 4
wi 5 3 8 2
vi 1 6 9 5
i=3 まで
暫定重さ合計 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
達成できる最大価値 0 - - 6 - 1 - - 9 - - 15 - 10 - -
をもとに、i=4 （w4 = 2, v4 = 5）を更新
j=0
暫定重さ合計 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
達成できる最大価値 0 --> 5 6 - 1 - - 9 - - 15 - 10 - -
更新
j=1
暫定重さ合計 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
達成できる最大価値 0 [-] 5 6 - 1 - - 9 - - 15 - 10 - -
作れないのでスキップ
j=2
暫定重さ合計 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
達成できる最大価値 0 - 5 -->10 1 - - 9 - - 15 - 10 - -
更新?
この $DP[2]=5$ というのは、先ほど $j=0$ から $4$ 番目の品物自体を選んだことによって更新された値なので、 それを元にさらに更新してしまうと、品物を2個選んだことになってしまう。
この問題は、$j$ を大きい方から更新することで、解消される。
j=13
暫定重さ合計 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
達成できる最大価値 0 - - 6 - 1 - - 9 - - 15 - 10 -->15
更新
j=12
暫定重さ合計 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
達成できる最大価値 0 - - 6 - 1 - - 9 - - 15 [-]10 - 15
作れないのでスキップ
j=11
暫定重さ合計 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
達成できる最大価値 0 - - 6 - 1 - - 9 - - 15 -->20 - 15
更新
...
初期値
ナップサックでは、重さの和が「$W$ 以下」で最も高い価値が求められることが多いが、 たまに「$W$ ちょうど」を要求されることもある。
“ちょうど” の場合は、DP配列の初期値は全て $-\infty$ としておいて、最初に $DP[0][0]=0$ だけ設定する。
$-\infty$ は、ここまでの品物の組み合わせではどうやってもその重さが作れないことを示す。
“以下” の場合は、初期値を全て $0$ としておくと（わずかだが）便利。
$-\infty$ とすると、最後に1度 $DP[N][\cdot]$ の最大値を調べる必要があるが、
初期値を $0$ としておくことでそうせずとも $DP[N][W]$ に答えが入っている。
選び方の復元
「最大価値を達成できる選び方も1つ求めよ」という問題の場合、DPは2次元で実装しておく。
DP配列を埋め終わったあと、$i=N,j=W$ から配列を逆向きにたどっていく。
- $N$ 番目の品物は採用して良いか？ の判定
- $DP[i][j] = DP[i-1][j-w_N]+v_N$ か？
- 意味合い: 採用したとして、重さ・価値の残りを $i-1$ 個で作れるか？
採用できるなら $j←j-w_N$ に更新し（採用不可ならそのまま）、次は $i-1$ の場合を同様に調べる。
$i=0$ まで辿ったときに採用できたものが答え。
分枝限定法
ナップサック問題は、場合分けして $i$ を1つ減らした部分問題状態に再帰的に言い換えられる。
- $1,2,3,4$ の品物を選んで、$W$ に入れられる価値を最大化
- $1$ を入れる場合 → $2,3,4$ の品物を選んで、$W-w_1$ に入れられる価値 $+v_1$ を最大化
- $2$ を入れる場合 → $3,4$ の品物を選んで、$W-w_1-w_2$ に入れられる価値 $+v_1+v_2$ を最大化
- …
- $2$ を入れない場合 → $3,4$ の品物を選んで、$W-w_1$ に入れられる価値 $+v_1$ を最大化
- …
- $1$ を入れない場合 → $2,3,4$ の品物を選んで、$W$ に入れられる価値を最大化
- $2$ を入れる場合 → $3,4$ の品物を選んで、$W-w_2$ に入れられる価値 $+v_2$ を最大化
- …
- $2$ を入れない場合 → $3,4$ の品物を選んで、$W$ に入れられる価値を最大化
- …
ここで、例えば以下のような状況の時、
- 真の答えの下限（これより大きくなる可能性はあるが、これ未満になることはない暫定的な答え）$tmp$ が見つかっている
- 上記の分岐で $1$ を入れた後の場合分け「$i=2,3,4$ の品物を選んで、$W-w_1$ に入れられる価値 $+v_1$ を最大化」などから、部分問題の解の上限（これより大きくなることは絶対にない値 $x$）が計算できる
- $x \le tmp$ である
最も良い場合でも $tmp$ を更新できない以上、さらにその部分問題について、$i=2$ を選ぶ/選ばない場合･･････などと探索していくのは無駄である。
このように、部分問題に分割しつつ、枝刈りを行って範囲を絞っていく方法を、分枝限定法という。
この考え方を元にする場合は、DP配列を埋めていく形ではなく再帰関数で実装した方が（速度面を気にしないなら）わかりやすいか。
その場合も枝刈りとは別に、DPによる高速化は使える。
「$i$ 番目の要素まで調べて、残り容量が $W$」というペア $(i,W)$ が同じなら部分問題の答えも同じなので、
メモ化することで同じ部分問題を何度も解かなくて済むようにできる。
枝刈りの仕方
ざっくりとでいいので、実際に調べなくても部分問題の答えの上限が見積もれないといけない。
ナップサック問題は、「品物を “小数点個” 選ぶことも許容する」問題ならすぐ解ける。
重さあたりの価値が大きい方から詰めていき、1個まるごと詰められなくなったら“0.75個”とかで残りを埋めればそれが最大価値となる。
そして、実際の答えは必ずそれ以下となる。
このように問題の制約を緩めて、実際の答えの上限を求めやすくした問題を、分枝限定法の文脈では「緩和問題」という。
緩和問題の答えですら $tmp$ に届かないなら、当然、実際の答えも届かない、という理屈。
緩和問題は問題毎に決まった1つがあるわけではなく、 精度の良い（実際の答えに近い見積もり値が得られる）ものを使えば枝刈りも効率的に行える。
ナップサック問題は、まぁ上記の緩和問題が精度も良く、求めやすいのでよく使われる。
その他
問題設定が単純なので、制約や条件を変更することで、さまざまな解法があり得る。
半分全列挙
「$W$ の範囲も $V$ の範囲もでかくてDPは無理だが、$N$ は最大でも $40$ くらい」という場合に使える。
品物を半分個して2グループA,Bに分け、それぞれのグループで {使う, 使わない} の愚直な全探索を行う。
$N$ のままだと $O(2^N)$ は無理だが、半分にすることで $O(2^{N/2})$ となり、間に合う規模になる。
(重さの和, 価値の和) の組み合わせが $2^{N/2}$ 個できる。
これをちょっと整理する。
- 1グループの結果の時点で $W$ を超えているものは除外
- グループごとに、同じ重さなら価値が最も大きいののみを残す
- グループBを重さでソート後、価値を先頭から見ていき、累積MAXを更新する要素のみ残す
これで、グループBは「容量 $W$ が $w_i \le W \lt w_{i+1}$ の範囲にあるなら最大価値は $v_i$」がわかる一覧になった。
グループAの各要素 $(w,v)$ につき、$W-w$ を超えない重さをグループBから探す。
二分探索を使えば1回につき $O(\log{2^{N/2}})→O(N)$ しかかからないので、Aの全要素を試しても $O(N2^{N/2})$ で済む。
全組み合わせで一番大きいものが答え。
線形計画問題として解く
少し解法という話からは逸れるかも知れないが、 ナップサック問題は線形計画問題として表現できるため、 線形計画問題の解法を使うこともできる。
ただし、一般に線形計画問題を解くのは これまでのナップサック問題に特化した解法と比べると 時間がかかったり、解法によっては稀に誤った答えを返すため、その点は留意する必要がある。
ただ、ソルバーが豊富にあるので（PythonならPuLPなど）、
制約的に $N$ が大きくない規模で、楽に実装したいよ、という場合は使える。
- $N$ 個の変数 $x=(x_1,x_2,...,x_N)$ がある
- その変数を使った線形不等式の形での制約が何個かある
- $3x_1+10x_2+2x_3 \le 11$
- 同様に線形で表された式の値を、制約に違反しない範囲で $x$ を上手く決めることで、最大化する
- $f=9x_1+3x_2+5x_3$
ナップサック問題では、$x$ が各品物を選ぶか選ばないかの0 or 1をとる変数となる。
制約の係数が重さ、$X$ がナップサック容量、最大化する式の係数が価値となる。
これなら、例えば制約にさらに値段が加わって、「重さ合計 $W$ 以下、値段合計 $P$ 以下で価値を最大化」みたいになっても、方針を変えないで解ける。
バリエーション
冒頭の問題は特に「0-1ナップサック」とも呼ばれるもので、各品物は1つだけという前提がある。
それ以外の個数や、他の条件があるナップサック問題も存在する。
各品物は何個もある
同じ種類の品物が何個でもある場合、0-1ナップサックとほぼ同様に解ける。
0-1ナップサックを1次元で実装する際の注意 「$j$ の小さい方から更新していくと、同じ品物を複数選んだことになってしまう」がこの場合は逆に有効に働くため、 $j$ の小さい方から更新していけばよい。
計算量は $O(NW)$ または $O(NV)$
個数制限付きナップサック問題
$i$ 番目の品物は $c_i$ 個だけある。というのが各 $i$ に決まっている場合の問題。
何個でもある場合と違い、$j$ の小さい方からの更新だと、今、品物を何個使ったのかわからなくなってしまう。
かといって、各 $j$ からそれぞれ $c_i$ 個入れるかどうかを試していては、 $c_i$ を均した値を $c$ として、$O(NWc)$ などの計算量がかかってしまう。
スライド最大値
スライド最大値というテクニックを用いると、$O(NW)$ または $O(NV)$ で解ける。
スライド最大値は、尺取法のように、ある連続した区間の最大値を求めながら、区間の左端と右端を徐々に進めていく場合に使えるテクニックである（下記リンク等参照）。
DPの更新において、遷移元・遷移先は「$j$ を $w_i$ で割ったあまりが同じ同士」にグループ化できる。
$j$ から更新されるのは $j+w_i,j+2w_i,j+3w_i,...$ といった感じ。
このグループ毎に更新を行う。
わかりやすくするため、DPから現在着目中のグループの要素だけを抜き出してみる。
wi=5、あまりが3同士のグループのとき j 3 8 13 18 23 28 ... j//wi 0 1 2 3 4 5 ... DP[i][j] 9 2 11 13 14 19
もらうDPで考えると、たとえば $c_i=3$ のとき、$DP[i+1][28]$ の値は、
- $DP[i][13]+3v_i$
- $DP[i][18]+2v_i$
- $DP[i][23]+v_i$
- $DP[i][28]$
この中の最大値と計算できる。また、$DP[i+1][33]$ はで以下となる。
- $DP[i][18]+3v_i$
- $DP[i][23]+2v_i$
- $DP[i][28]+v_i$
- $DP[i][33]$
なので、$d_j=\frac{j}{w_i}$（切り捨て）として、以下のようにあらかじめ $d_jv_i$ を引いておけば、
- $DP[i][3]$
- $DP[i][8]-v_i$
- $DP[i][13]-2v_i$
- $DP[i][18]-3v_i$
- …
$DP[i+1][j]$ の値は、これらの値の自身から $c_i$ 個前までの $c_i+1$ 個中の最大値に、$d_jv_i$ を足した値として求められる。
2のべきで個数を分割
$c_i$ を2のべき（と余り）に分割する。たとえば $c_i=36$ なら、$1+2+4+8+16+5$ に分割できる。
すると、「$i$ 番目の品物1個セット」が1個、「2個セット」が1個、「4個セット」が1個、、、という
約 $\log{c_i}$ 個のセットの0-1ナップサックに置き換えることができる。
（当然、セットの $w_i,v_i$ は品物の個数分倍加される）
2のべきに分割することで、$1～c_i$ までのどんな個数もこれらのセットの組み合わせで作れることが保証される。
よって、$O(NW\log{c})$ で計算できる。（$\log{c}$ は各 $\log{c_i}$ を均した値）
元の0-1ナップサックからコードを変更する箇所が少ないので実装しやすく、 また、$c_i=1～3$ などの個数の少ない品物が多い場合は、定数倍のためにこちらの方が高速になることもある？
一度入れたアイテムを除く
クエリ問題などで、既に考慮に入れたアイテムを除きたい場合。
適用条件
通常のナップサックでは難しいが、「個数を求める部分和問題(※)」など、問題設定によっては可能。
（※ $N$ 個の整数 $a_1,...,a_N$ から合計が $W$ となるように選ぶ方法の個数）
両者の違いは、DPの値の更新が通常は min, max だが、選び方を求める問題では加算(+)となる点。
$\max(A,B)=C$ のようにmaxによる更新の場合、$B$ と $C$ が分かっていても $A$ を復元することはできないが、
$A+B=C$ のように加算なら、$B,C$ から $A$ を復元できる。
このように、二項演算 $A \oplus B = C$ で、$B,C$ から $A$ を復元できるような更新をするナップサック問題なら可能。
方法
ナップサック問題は、通常、アイテムを入れる順番は関係ないので、 取り出したいアイテムは、直前に限らずどの時点で入れたアイテムであってもよい。
特に難しいことは無く、通常の更新を逆にたどるとよい。
- $DP[i,j]=i$ 個目のアイテムまで考慮して、和が $j$ となる方法の個数
として、$i+1$ 番目の $x$ を“追加”しようとするとき、上限を $W$ として、以下のようになる。
j 0 1 ... x x+1 ... W-x ... W
DP[i] a b ... c d ... e ... z 自身を x 個ずらした値と
+ a b ............ e 足し合わせる
-----------------------------------
DP[i+1] a b ... a+c b+d .......... e+z
“除外” する操作は、上記の $i+1$ が分かっている状態から $i$ を復元するようにしたいということなので、
- $DP[i,0～x-1]$ は $DP[i+1,0～x-1]$ と等しい
- $DP[i,x]=DP[i+1,x]-DP[i,0]$（上記、$(a+c)-a=c$）
- $DP[i,x+1]=DP[i+1,x+1]-DP[i,1]$（上記、$(b+d)-b=d$）
- …
というように、小さい方からずらして引いていけばよい。
現状、解くのが難しい問題
多次元ナップサック問題
重さ以外にも、値段とか体積とか（設定は何でもいいが）の制約がある中で、価値を最大化する問題。
通常の $KP$ が $\mathcal{N}\mathcal{P}$-困難であることから，MDKP が $\mathcal{N}\mathcal{P}$-困難であることも自明である．さらに通常の $KP$ が完全多項式オーダーの近似解法が存在するのに対し，MDKPでは，2 次元でさえも完全多項式の近似解法が ($\mathcal{P}\neq \mathcal{N}\mathcal{P}$ の仮定のもとでは) 存在しないことが証明されている．また，ヒューリステイツク解法においても，精度が安定したアルゴリズムが少なく，適当な下界値を得ることも困難を要する問題であることが知られている．
動的計画法を用いた多次元ナップサック問題の変数縮小法, 2012
あまりちゃんと理解していないが、全探索以上の上手い解法は相当難しそう。
複数ナップサック問題
ナップサックが複数ある。当然だが、品物を2つに割って別々のナップサックに入れることはできない。
こちらも効率的に解くのは難しいっぽい。
ナップサックも、同じサイズだったり、それぞれにコストが定められた別々の容量のナップサックだったりとさらなるバリエーションがある。
