競プロ的ナップサック問題11問

おそらく、競プロでは最も基本的な制約パターンです。

小問題 $f(i,w)$ を次で定めます。

$f(i,w)$ : 品物の種類のうち先頭 $i$ 個のみ考慮するとして、重さの合計が $w$ 以下のときの価値の合計の最大値。 ($0\leq i\leq N$ , $0\leq w \leq Z$)

種類 $i$ の品物に対しては、持ち帰る個数を $0$ にするか $1$ にするかだけの選択肢があります。この選択肢それぞれについて、種類 $1,2,\ldots ,i-1$ の品物の選び方にかかる条件を確かめることで、次の漸化式を得ます。

この漸化式の通りに計算すれば、計算量は $O(NZ)$ です。

同じ種類の品物を何個でも選んでよいような個数設定です。

小問題 $f(i,w)$ を次で定めます。

$f(i,w)$ : 品物の種類のうち先頭 $i$ 個のみ考慮するとして、重さの合計が $w$ 以下のときの価値の合計の最大値。 ($0\leq i\leq N$ , $0\leq w \leq Z$)

種類 $i$ の品物の個数で場合分けすると漸化式は $f(i,w)=\min\left\lbrace f(i-1,w), f(i-1,w-W_i)+V_i, f(i-1,w-2W_i)+2V_i, \ldots \right\rbrace$ となります。このままでは計算量が悪化しますが、 $\min$ が間隔 $W_i$ の累積 min で表せることを利用して改善できます。これにより、以下の漸化式を得ます。

この漸化式の通りに計算すれば、計算量は $O(NZ)$ です。

品物の多重度が入力で与えられます。この制約は、 (1)(2) をカバーします。

まず (1)(2) で使ったものと同じ小問題を考えます。

$f(i,w)$ : 品物の種類のうち先頭 $i$ 個のみ考慮するとして、重さの合計が $w$ 以下のときの価値の合計の最大値。 ($0\leq i\leq N$ , $0\leq w \leq Z$)

種類 $i$ の品物の個数で場合分けすると漸化式は $f(i,w)=\min\left\lbrace f(i-1,w), f(i-1,w-W_i)+V_i, \ldots , f(i-1,w-M_iW_i)+M_iV_i \right\rbrace$ となります。

$W_i=1$ の場合、 $f(i,w)$ は、 $f(i-1,w)-wV_i$ に対してウィンドウ幅 $M_i$ のスライド最大値になっています。 $W_i\neq 1$ の場合は、 $f(i-1,*)$ を $W_i$ 間隔で取り出せば同様にできます。

スライド最小値は線形時間で計算できるので、 $f(i-1,*)$ から $f(i,*)$ を計算量 $O(Z)$ で得ることができます。

全体の計算量は $O(NZ)$ です。

スライド最小値のアルゴリズムは単調な deque を管理する方法が標準的ですが、ウィンドウの幅が一定である今回の用途では、単に配列を用いた単純な操作で実装できます。

連続する $M_i+1$ 要素の最小値を求める部分がメインです。配列を $M_i$ 要素ずつに区切ると、最小値を求めたい区間はそれぞれちょうど $1$ 回境界をまたぎます。そこで、配列を $M_i$ 要素ずつに区切った区間内で左からの累積最小値と右からの累積最小値を計算して $2$ つの配列に格納すれば、必要な区間最小値はこれらの配列から $1$ つずつ取り出した $2$ 要素の最小値で表せます。これでスライド最小値を $O(NZ)$ 時間で計算できます。

品物の選び方の重さとして現れる値が非常に多く、 (1)～(3) で説明したような方法がとれません。代わりに価値で選び方を分類します。

ナップサック問題の答えが $\text{ans}$ であるとは、「重さ $Z$ 以下で価値 $\text{ans}$ 以上の選び方」は存在するが「重さ $Z$ 以下で価値 $\text{ans}+1$ 以上の選び方」は存在しないということです。「重さ $x$ 以下で価値 $y$ 以上の選び方」が存在するかどうかについて、 $x$ を固定して $y$ の最大値を見るのが (1)～(3) での方針でしたが、 $y$ を固定して $x$ の最小値を見ることもできます。

次の小問題を考えます。

$f(i,v)$ : 品物の種類のうち先頭 $i$ 個のみ考慮するとして、価値の合計が $v$ 以上のときの重さの合計の最小値。 ($0\leq i\leq N$ , $0\leq v$)

価値合計は最大で $NV$ になります。よって、素直な DP の計算量は $O(N^2V)$ です。

指数時間かけて何とかする方向性の制約設定です。

$N$ 個の品物を $2$ つのグループ ( $\lfloor N/2\rfloor$ 個と $\lceil N/2\rceil$ 個) に分け、それぞれあり得る選び方を全列挙します。

品物 $n$ 個のグループでは品物の選び方は $2^n$ 通りあるので、 $2^n$ 通りそれぞれ ( 重さの総和 , 価値の総和 ) を計算し、重さの総和で昇順ソートしたものを求めます。一度に列挙するのではなく、 $n=0$ から品物を $1$ 個ずつ増やしながら、都度重さの総和で昇順ソートされた状態を保つことにします。すると品物を増やしたときの処理は次のようになります。

1. 品物を採用する・しないの $2$ つに分岐させたそれぞれがソート済み列になる
2. $2$ 個のソート済み列のマージ

これは線形時間でできます。よって、 $2^n$ 通りの列挙して重さで昇順ソートしたものは、計算量 $O(2^n)$ で求まります。

各グループのソート済み列を先頭から見て、価値最大が更新されないような要素を削除します。削除した要素は、より重さが小さいが価値は小さくないような他の選び方があるので、考慮不要です。これにより、列内では価値が単調増加になります。

$2$ つのソート済み列を $\alpha$ , $\beta$ とすると、 $\alpha$ から要素 $(w,v)$ を選ぶ場合には、 $\beta$ から選べる要素は重さ $Z-w$ 以下のものです。それが存在する場合、重さ $Z-w$ 以下ギリギリの要素を取り出せば、その要素の価値が価値最大です。 $\alpha$ の要素を重さ昇順に走査すると重さギリギリの $\beta$ の要素は $\beta$ の重さ降順に現れるので、計算量は $O(|\alpha|+|\beta|)$ です。

全体の計算量は $O(2^{N/2})$ です。

ナップサックの容量のうち、 $K$ で割ったあまりの部分は、重さ $1$ の品物でしか利用できません。よって、まず重さ $1$ の品物を価値が大きい順に $(Z\bmod K)$ 個取り、無条件に採用します。

ここでもし重さ $1$ の品物を追加で $1$ 個でも採用する場合、価値が大きい順に $K$ 個一度に採用する場合に帰着します。よって、残った重さ $1$ の品物は価値の降順に $K$ 個ずつまとめて重さ $K$ の品物に変換できます。そうすると $Z$ も $W_i$ もすべて $K$ の倍数になるので、それぞれ $K$ で割って残りの問題を解けます。

品物の個数は新しく表れる仮想的なものも合わせて $O(N)$ です。全体の計算量は $O(N\log N+\log Z)$ です。

まず $M_i=1$ の場合に帰着させます。例えば、重複度 $M_i=12$ の品物があるとき、 $1,1,2,4,4$ 個の $5$ つに分け、それぞれ $1$ つの品物とみなすと、この $5$ つの組み合わせで $0$ ～ $12$ 個を表現できるので、最適値は変わりません。具体的には、重複度 $M$ ($3\leq M$) の品物は $((M+1) \bmod 2) +1$ 個残し(高々 $2$ 個)、それ以外を重さと価値がそれぞれ $2$ 倍の品物として扱うことができます。この操作の繰り返しにより、品物の合計個数が $O(N\log Z)$ であるような同制約の問題に帰着します。

下位桁から DP します。

まず $t_i=1$ の品物のみで、 $f(1,w)$ : 重さの総和が $w$ 以下のときの価値の総和を ($0\leq w\leq \sum W_i$) 計算します。 $\sum W_i$ が $O(\sum{s_i})$ になるので、この部分の計算量は $O(N\sum{s_i})$ つまり $O(N^2(\max s_i))$ です。残った品物は重さがすべて $2$ の倍数なので、 $(Z\bmod 2)$ の部分を処理したのち重さをすべて $2$ で割った問題に帰着します。 $f(1,*)$ から影響するのは $f(1,2w+(Z\bmod 2))$ の部分だけなので、元の DP テーブルのサイズの $1/2$ 倍が次の問題に引き継がれます。同様に DP と問題の帰着を繰り返して $Z=0$ になったときに解が得られます。

計算量は $O(N^2(\max s_i)\log Z)$ です。

重さの制約が代わりに $W_i=s_i\times K^{t_i}$ である場合は、品物 $1$ 種類の変換後の各層において、個数 $O(\log K)$ 、合計重さ $O(K\max s_i)$ とすることができ、その場合の計算量は $O((N\log K)(NK\cdot \max s_i)\log_K Z)$ ^(*1) つまり $O(N^2K(\max s_i)\log Z)$ になります。

(*1) 掛けられている $3$ つの要素はそれぞれ、変換後の各層の品物の個数、各層で行う DP における仮想的なナップサック容量、層の個数です。

$Z$ の割に $W_i$ が小さく、品物の重複度は無限であるという場合です。このような場合では、大部分を最も効率がよい品物で埋め、それでピッタリの重さにならない場合は他の品物を使って少しつじつま合わせをするという感じの解が最適になります。

$V_i/W_i$ が最大となる品物を品物 $\mathrm{P}$ : $(V_\mathrm{P},W_\mathrm{P})$ として、品物 $\mathrm{P}$ 以外の品物を採用する個数が $W_\mathrm{P}$ 未満であるような最適解が存在することを示します。

最適解において品物 $\mathrm{P}$ 以外の品物を採用する個数は最小でも $W_\mathrm{P}$ であると仮定し、矛盾を導きます。そのような最適解において品物 $\mathrm{P}$ 以外で採用した品物を一列に並べ、先頭から $i$ 個の重さの総和を $Y_i$ とします。鳩ノ巣原理より、 $Y_0,Y_1,\ldots ,Y_{W_\mathrm{P}}$ のそれぞれを $W_\mathrm{P}$ で割ったあまりには重複があります。それを $Y_a,Y_b$ ($a\lt b$) とすれば、 $a$ 番目から $b-1$ 番目の品物と $(Y_b-Y_a)/W_\mathrm{P}$ 個の品物 $\mathrm{P}$ を交換でき、品物 $\mathrm{P}$ は $V_i/W_i$ が最大であることから価値の総和が減少しません。この交換により、品物 $\mathrm{P}$ 以外の品物を採用する個数が少ない最適解が得られるため、仮定に矛盾します。

$Z$ が $(\max W_i)^2$ よりも大きいので、 品物 $\mathrm{P}$ 以外の選び方を任意に選び、その重さを $(v,w)$ としたときの $v+\left\lfloor (Z-w)/W_\mathrm{P}\right\rfloor V_\mathrm{P}$ としてあり得る最大値が解です。ここで次の小問題を考えます。

$f(i,w)$ : 品物 $\mathrm{P}$ 以外のうち $i$ 種類目までの選び方について、重さを $w^{\prime}$ 、価値を $v^{\prime}$ としたとき、 $w^{\prime}\bmod W_{\mathrm{P}}=w$ となる場合の $v^{\prime}+\left\lfloor (Z-w^{\prime})/W_\mathrm{P}\right\rfloor V_\mathrm{P}$ の最大値 ($0\leq i\leq N-1$ , $0\leq w\leq W_{\mathrm{P}}-1$)

最大値を取れるのは $w\leq (\max W_i)^2\lt Z$ の場合のみなので、小問題の解として、 $Z-w^{\prime}$ を負にしなければならないような無効なものは現れません。

$f(i,*)$ から $f(i+1,*)$ を計算するには、計算順に気を付けながら $2$ 周するように更新すればよいです。この計算量は $O(\max W_i)$ です。より具体的には、更新されていない $w$ を見つけて $w_0$ とすると、 $w_0\rightarrow (w_0+W_i)\bmod W_\mathrm{P} \rightarrow (w_0+2W_i)\bmod W_\mathrm{P} \rightarrow \ldots$ の順に $2$ 周分更新します。

以上より、この特殊設定の問題は計算量 $O(N\max W_i)$ （または $O((\max W_i)^2)$）で解けます。

次の小問題を考えます。

$f(i,w)$ : 重さ $i$ 以下の品物のみ考慮する。重さが $w$ 以下である選び方における価値の最大値。

$f(i-1,w)$ から $f(i,w)$ を計算するときは、次式を計算することになります。

• $q_{i,k}$ は、重さ $i$ の品物を最大 $k$ 個まで選んだときの価値の最大値とする。
• $f(i,w)=\max_{0\leq k, ki\leq w}f(i-1,w-ki)q_{i,k}$

このとき、

• $q_{i,0},q_{i,1},q_{i,2},\ldots$ は上に凸である。 ( $q_{i,a}-q_{i,a-1}\geq q_{i,a+1}-q_{i,a}$ )
• $f(i,*)$ を $i-1$ 個飛ばしで読んだ列は、 $f(i-1,*)$ を $i-1$ 個飛ばしで読んだ列と $(q_{i,0},q_{i,1},q_{i,2},\ldots)$ の max-plus convolution である

となります。片方の列が上に凸である場合の max-plus convolution は、 SMAWK アルゴリズムを用いて線形時間で計算できます^(*1)。従って、 $f(i-1,w)$ ($0\leq w\leq Z$) から $f(i-1,w)$ を $O(Z)$ 時間で計算できます。

全体の計算量は $O(Z|\lbrace W_i\rbrace |+N\log N)$ です。 ($|\lbrace W_i\rbrace |$ は異なる $W_i$ の値の個数)

(*1) ですが、 SMAWK アルゴリズムを丁寧に実装するよりも、計算量の $\log Z$ 倍を許して、計算量 $O(n\log n)$ 時間 ($n$ は行列の周長)の monotone minima を使用するほうが、実行時に高速だったりそうでなかったりします。実装例では monotone minima を使用しているため、計算量は記載のものと異なります。

(8) と同様に、貪欲法による解の近傍に最適解が存在することを利用します。

$V_i/W_i$ が大きい品物から順に採用してゆき、次の品物で重さが $Z$ を超えるようになったら止めるという方法で採用された品物の(多重)集合を $A$ 、採用されなかった品物の(多重)集合を $B$ とします。

採用した品物のうちのいくつか(これを $\alpha$ とする)と、採用しなかった品物のうちのいくつか(これを $\beta$ とする)を選び、 $A-\alpha+\beta$ が最適解になる場合を考えます。このとき、 $\alpha$ で選ばれる品物の個数の最小値は $\max W_i$ 未満になります。よって、 $\alpha$ の重みは $(\max W_i)(\max W_i-1)$ 以下、 $\beta$ の重みは $(\max W_i)^2$ 以下のケースさえ考慮できれば、入れ替えで得られる解の中に最適解の一つが含まれます。

あとは、次の $2$ つが求まればよいです。

れぞれ、 $h=1,2,\ldots $ の順に重さ $h$ の品物を考慮に加える形の DP で計算できます。また、そこで現れる max-plus convolution および min-plus convolution に SMAWK アルゴリズム^(*1)を用いることができ、従って $2$ つの DP はそれぞれ $O((\max W_i)^3+N\log N)$ 時間で完了します。

最後に、 $A$ の重みを $W_A$ 、価値を $V_A$ として、 $g(z+(Z-W_A))-f(z)+V_A$ の最大値を求めればそれが解になります。

(*1) (9) で言及したことの繰り返しですが、 monotone minima の計算量 $O(n\log n)$ ($n$ は行列の周長) の方法のほうが実際上高速の場合があります。

(10) と同様です。

$V_i/W_i$ が大きい品物から順に採用してゆき、次の品物で重さが $Z$ を超えるようになったら止めるという方法で採用された品物の(多重)集合を $A$ 、採用されなかった品物の(多重)集合を $B$ とします。 $A$ の部分集合 $\alpha$ 、 $B$ の部分集合 $\beta$ を取り、 $A-\alpha+\beta$ を新しい解とするとき、 $\alpha$ の価値が $(\max V_i)(\max V_i-1)$ 以下である範囲に最適解が存在します。

あとは、次の $2$ つが求まればよいです。

これらの値は、 SMAWK アルゴリズム^(*1)を用いる方法により $O((\max V_i)^3+N\log N)$ 時間で求まります。

最後に、 $A$ の重みを $W_A$ 、価値を $V_A$ として、ある $z$ について $W_A-f(z)+g(z+\delta) \leq Z$ を満たす $\delta$ の最大値 ($0\leq \delta\lt \max V_i$) を求めれば、 $V_A+\delta$ が解になります。

(*1) (9) で言及したことの繰り返しですが、 monotone minima の計算量 $O(n\log n)$ ($n$ は行列の周長) の方法のほうが実際上高速の場合があります。

[詳細未確認] (10) の設定において、 $W:=\max W_i$ として、追加の制約 $M_i=1$ が課される場合の計算量は $O (N+W^2(\log W)^4)$ [1]まで改善されていて、また $M_i$ に追加の制限がない場合についても計算量 $\tilde {O} (N+W^2)$ [2]が示されています。(どちらも、 (11) については $W :=\max V_i$ として同様の計算量になるらしい)

Aizu Online Judge の”コース”に、やけにナップサック問題に詳しいカテゴリがあります。 AtCoder Beginner Contest にナップサック問題系の問題が出たため、 AOJ のコースの問題の制約をまとめた画像を Twitter に投稿すると、さらに知見をリプライでいただきました。そもそも AOJ の問題の解説もアクセスしづらい（少なくとも元の問題にはリンクされていない）こともあり、追加分も含めて一つの投稿にまとめようと思いました。