はじめに
競技プログラミングではナップザック問題(Wikipedia:ナップザック問題)が出題されることがあります。
ナップザック問題は解き方を習得しておかないと中々解けない問題であり、幾つかあるバリエーションを理解できていないととても制限時間内には解けない問題だと思います。
[1]ではナップザック問題を丁寧に解説されているものの、私のように分からない者には結構ギャップがあると感じています。そんな動機で自分が感じているギャップをまとめてみました。
題材としては、AtCorder Problemに出題されている問題[2]を使わせていただきます。と言うのも、この問題で分かっているつもりが実は理解できていないことを教えてもらったからです。
この問題を解くには、基本的なナップザック問題に以下の条件が加わります。
- 商品個数を無制限に選べる
- ペナルティが付く
１．基本パターン
まずは、本題の問題を解く前に基本的なナップザック問題の解き方を見てみます。
ここでは参考文献[1]に書かれている解き方を参考にしました。
問題
重さと価値がそれぞれ、$w_i$、$v_i$であるようなN個の商品があります。これらの商品から、重さの総和が W を超えないように選んだときの、価値の総和の最大値を求めなさい。
N = 4、W = 5
(w, v) = {(2, 3), (1, 2), (3, 4), (2, 2)}
これを総当たりで解くと以下のようになります。
N = 4
WV = [(2,3),(1,2),(3,4),(2,2)]
W = 5
D = {}
def res(i,j):
print(f'i: {i:02d} j:{j:02d}')
if i>=N: return 0
w, v = WV[i]
if j<w : return res(i+1, j)
else: return max(res(i+1,j),res(i+1,j-w)+v)
print(res(0,W))
下図は res() が呼び出された ($i$, $j$)の組合せになります。（青いラベルのある個所）
同じ ($i$, $j$) の組合せで呼ばれている箇所があります。
更に、商品毎に res() が呼び出される回数を見ると、2回、4回、7回、12回と$\mathcal{O}(2^n)$で増えています。
厳密に$2^n$にならないのは、重さで抑えている下記コードによります。
if j<w : return res(i+1, j)
これをDPを使って解くと以下のようになります。
N = 4
WV = [(2,3),(1,2),(3,4),(2,2)]
W = 5
dp = [[0 for _ in range(W+1)] for _ in range(N+1)]
for i in range(0, N):
w, v = WV[i]
for j in range(0, W+1):
if j<w: dp[i+1][j] = dp[i][j]
else: dp[i+1][j] = max(dp[i][j], dp[i][j-w]+v)
print(dp[-1][W])
この方法であれば、処理時間は$\mathcal{O}(商品数{\times}重さ)$となり、総当たりよりも速く処理できると期待できます。
DPで上手く解けるのは以下の理由です。
まず、上記プログラムで作る dpテーブルの内容は下図のようになります。
dp[i+1][j]の意味は、以下になります。
$i$ 行は、$i$ 番目の商品の価値を使ってdp[i+1]行目に価値を入れます。
一方j列は、袋を徐々に最大になるまで広げながら、商品を積み重ねて行くイメージになります。
dp[i+1][j]の処理には以下のケースがあります。
（１）商品の重さ $w_i$ が、その時点での袋の重量を超えてしまうケース
（２）商品の重さ $w_i$ が、その時点での袋の重量に納まるケース
（１）は、商品 $i$ を使えないので、dp[i+1][j]はdp[i][j]と同じになります。
（２）は商品 $i$ を利用できるものの、商品 $i$ を使う場合と使わない場合で価値を比較します。
（３）使わない場合の価値は（１）同様、dp[i][j]となります。
（４）使う場合の価値は、現在の重量 $j$ より商品 $i$ の重さ $w_i$ 少ない時点の価値に商品 $i$ の価値 $v_i$ を加えた値になります。
したがって、（２）の値は（３）と（４）の大きい方となります。
２．応用パターン（１）商品個数制限なし
再び[1]を参考にします。
問題
重さと価値がそれぞれ、$w_i$、$v_i$であるようなN個の商品があります。これらの商品から、重さの総和が W を超えないように選んだときの、価値の総和の最大値を求めなさい。
ただし、同じ種類の商品をいくつも選ぶことができます。
N = 3、W = 7
(w, v) = {(3, 4), (4, 5), (2, 3)}
プログラム化の前に定義を式変形します。定義からdpは以下のようになります。
dp[ i+1 ][ j ] =
max( dp[ i ][ j - k${\times}$w[ i ] ] + k${\times}$v[ i ] | 0${\leqq}$k )
k=0のケース dp[ i ][ j ]をくくり出す。
max( dp[ i ][ j ] , dp[ i ][ j - k${\times}$w[ i ] ]+k${\times}$v[ i ] | 1${\leqq}$k )
max関数の後半部分の最大値を求める式として変形します。
w[ i ] を w、v[ i ]を v と置き換えます。
k - 1 を h で置き換えます。
max( dp[ i ][ ( j - w ) - h${\times}$w] + h${\times}$v | 0${\leqq}$h ) + v
v がmax関数の外に出たのは、h = k+1であり、v の分だけ常に加えられるからです。
max( dp[ i ][ ( j - w ) - h${\times}$w] + h${\times}$v | 0${\leqq}$h ) は dp[ i+1 ][ j - w ] の定義になっています。
上記から、以下のようになります。
dp[ i + 1][ j ] = max( dp[ i ][ j ] , dp[ i + 1 ][ j - w[ i ] ] ) + v[ i ]
これをプログラムで表すと以下のようになります。
N = 3
WV = [(3,4),(4,5),(2,3)]
W = 7
dp = [[0 for _ in range(W+1)] for _ in range(N+1)]
for i in range(0, N):
w, v = WV[i]
for j in range(0, W+1):
if j<w: dp[i+1][j] = dp[i][j]
else: dp[i+1][j] = max(dp[i][j], dp[i+1][j-w]+v)
print(dp[-1][W])
ここで、チョットした疑問がありました。
dp[i+1][j] を決める際に dp[i][j]とdp[i+1][j-w] を比べていますが、何故、i+1行目 なのかが分かりませんでした。
[1] では、直感的な説明として $k$ 個目の商品 $i$ の価値を決める際には、「既に計算済みの $k-1$ 個目の結果（＝dp[i+1][j-w]）と比較すれば良いので」と書かれていました。
これはこれで納得なんですが、基本パターンでは、dp[i][j-w]と $i$ 行目の比較なので、この違いにモヤモヤしていていました。
ただ、これは最初に商品 $i$ を袋に入れる際には、$i$ 行目と比較しており、最初と２個目以降の違いなのかと納得をしています。（下図参照）
３．応用パターン（２）ペナルティあり
最後に本題について考えてみます。ここでは[2]の解説を参考にしました。
問題：AtCorder Problem ABC373 F
N種類の品物があり、$i$ 種類目の品物の重みは$w_i$価値は$v_i$です。どの種類の品物も $10^{10}$個ずつあります。これから、品物をいくつか選んで、容量 W の袋に入れます。選ぶ品物の価値を大きくしつつ、同じ種類の品物ばかりにならないようにしたいです。そこで、$i$ 種類目の品物を$k_i$個選んだときの 価値を$k_iv_i−k_i^2$と定義したとき、選んだ品物の重さの総和を W 以下にしつつ、価値の総和が最大になるように品物を選びます。価値の総和の最大値を求めてください。
問題文の表現を若干変更しています。
明確には書かれていませんが、以下の条件が含まれています。
（１）同一商品を複数回選ぶことができる
（２）同じ重さの異なる商品がある（←ペナルティがここで効いてきます）
応用パターン（１）にペナルティの考え方を入れれば解くことができるはずです。
応用パターン（１）では、$k$ 個目の商品$i$ を追加する際に、価値 $v_i$ を無条件に加えていますが、ここで２つのことを考える必要があります。
（３）同じ商品を複数回袋に入れる際にはペナルティがある
（４）同じ重さの異なる価値の商品がある
まず、（３）について、価値が4の時は個数によって価値は以下のように変わります。
応用パターン（１）では、（$i$, $j$）の価値が漸化式で表現ができ、直前の計算結果を利用することができましたが、個数によって価値が変わることから、（$i$, $j$）の価値計算の度に商品 $i$ が０個使われる場合、１個使われる場合...と計算する必要があります。
これをプログラムで表現すると以下のようになります。
ただし、以下の条件としています。
N = 3、W = 6
(w, v) = {(1, 4), (2, 3), (2, 7)}
def genValue(v):
L = [0 for _ in range(W+1)]
for k in range(W+1):
L[k] = k*v-k**2
return L
N, W = 3, 6
WV = [(1, 4), (2, 3), (2, 7)]
H = [genValue(WV[_][1]) for _ in range(N)]
dp = [[0 for _ in range(W+1)] for _ in range(N)]
for i in range(N):
w = WV[i][0]
V = H[i]
for j in range(W+1):
k = 1
result = 0
while 0 <= j-k*w:
result = max(dp[i-1][j]
,dp[i-1][j-k*w]+V[k]
,result)
k += 1
dp[i][j]=result
print(max(map(lambda x: max(x), dp)))
上記プログラムの genValue() は個数によって変わる価値のリストを作っています。
このリストを使って、商品（$i$）毎に袋の重さ（$j$）を大きくしながら、（$i$,$j$)の価値を求めています。
上記のプログラムでは（４）については考慮せず別商品扱いとしています。
この方法では重さ $j$ 毎に $j÷w_i$ 回（$i$, $j$）の価値計算をしており、$\mathcal{O}(商品数×袋の重さの2乗)$の計算量となることから効率の良い計算とはなっていません。
[2]のAtCorderの解説では、貪欲法、ヒープキュー：heapqを使い$\mathcal{O}(n)$で実装できる方法が解説されています。残念ながら、そこを解き明かすところまでは到達できませんでした。
４．さいごに
冒頭にも書きましたが、[1]のナップザック問題について一通り読んで理解したつもりで[2]の問題をやってみましたが、[2]の解説を読んでも、動画を見てもサッパリ分からず、そもそもナップザック問題の肝心なところが分かっていないことに気づかされました。
この投稿では、効率の良い解き方まで到達することができませんでしたが、幾つかのギャップについては解き明かすことができました。
効率化の問題は次の宿題とします。
５．参考文献
[1]：秋葉、岩田、北川著『プログラミングコンテストチャレンジブック』毎日コミュニケーションズ（2010年）
[2]：ABC373 F - Knapsack with Diminishing Values