個数制限付きナップザック問題
目次
/icons/hr.icon
問題
価値が $ v_i 重さが $ w_i であるような $ N 種類の品物と、容量が $ W のナップザックがあります。
次の条件を満たすように、品物を選んでナップザックに入れます。
選んだ品物の価値の合計をできるだけ高くする。
選んだ品物の重さの総和は $ W を超えない。
$ i 番目の品物は $ m_i 個まで選ぶことができる。
価値の合計の最大値を求めてください。
/icons/hr.icon
入力
$ N \quad W
$ v_1 \quad w_1 \quad m_1
$ v_2 \quad w_2 \quad m_2
$ \colon
$ v_N \quad w_N \quad m_N
/icons/hr.icon
制約
$ 1 \leq N \leq 100
$ 1 \leq v_i \leq 1000
$ 1 \leq w_i \leq 1000
$ 1 \leq m_i \leq 10000
$ 1 \leq W \leq 10000
/icons/hr.icon
考察
一般的な 個数制限無し ナップザック問題は$ O(NW)で簡単に解くことができます
良くあるド典型問題ですね。
しかし今回は 個数制限あり なので愚直にループを回すと今回の場合は $ O(NWM) となってしまい間に合いません。
ここで出てくるのがダブリングのような考え方です。
$ m_iを$ 2の冪乗ごとに分解し DP を回していくことで $ O(NW\log M)まで落とすことが出来ます。
一旦コードを共有します（言語化がむずかしい）
code:main.py
N, W = map(int, input().split())
for i in range(N):
v, w, m = map(int, input().split())
p = 1
while m > 0:
for j in reversed(range(w * p, W + 1)):
m -= p
p = min(2 * p, m)
print(max(dp))
/icons/hr.icon
初見だと何をやっているかわからないかもしれませんが、まず $ p という変数に $ m_iを$ 1,2,4,8,...といった感じに分解していきます。
そして$ 2の冪乗分を一気に DP で更新します。これを $ m_i が $ 0になるまで更新を続けます。
このようにすることで解くことが出来ました。
/icons/hr.icon
最後に
思いついた人天才ですな...
このすばのアニメがめっちゃ面白いので観てない人は必ず観ましょう。
終わりではない...
どうやらこの問題、$ O(NW)で解ける高度典型があるらしいです。勉強します...
/icons/hr.icon
$ O(NW)で解けるようになりたい
天才式変形
ここからは頑張って式変形をしてみます
$ {\mathrm dp}[i][j] を $ i番目までの商品で重さが$ jとなるような価値の最大値と定義します。
この際求める$ {\mathrm dp}テーブルの更新は以下のようになります
$ \begin{aligned} {\mathrm dp}[i][j] &= \max ({ \mathrm dp}[i - 1][j], {\mathrm dp}[i - 1][j - w_i] + v[i], {\mathrm dp}[i - 1][j - 2w_i] + 2v_i,\dots, dp[i - 1][j - m_iw_i] + m_iv_i ) \\ &= \max ( {\mathrm dp}[i - 1][j - kw_i] + kv_i ) \quad (0 \leq k \leq m_i, j - kw_i \geq 0) \end{aligned}
これ愚直に計算すると、$ O(NWM)なので落とす方法について考えます。
はじめに$ j = tw_i + pとなるような$ t, pを定めます。
すると上記の式は以下のようになります。
$ \begin{aligned} {\mathrm dp}[i][j] &= {\mathrm dp}[i][tw_i + p] \\ &= \max_k ( {\mathrm dp}[i - 1][tw_i + p - kw_i] + kv_i) \\ &= \max_k \left\{ dp[i - 1][(t - k)w_i + p] + kv_i \right\} \quad (0 \leq k \leq \min(t, m_i)) \end{aligned}
上記の式に$ tv_i - tv_iを加えます。
すると式は以下のようになります。
$ \begin{aligned} {\mathrm dp}[i][j] &= {\mathrm dp}[i][tw_i + p] \\ &= \max_k \left\{ dp[i - 1][(t - k)w_i + p] + kv_i \right\} \\ &= \max_k \left\{ {\mathrm dp}[i - 1][(t - k)w_i + p] + kv_i \right\} + (tv_i - tv_i) \\ &= \max_k \left\{ {\mathrm dp}[i - 1][(t - k)w_i + p] + kv_i - tv_i \right\} + tv_i \\ &= \max_k \left\{ {\mathrm dp}[i - 1][(t - k)w_i + p] - (t - k)v_i \right\} + tv_i \end{aligned}
ここで、$ q = t - kとすると、
$ \begin{aligned} {\mathrm dp}[i][j] = {\mathrm dp}[i][tw_i + p] = \max_q \left( dp[i - 1][qw_i + p] - qv_i \right) + tv_i \end{aligned}
ここで、$ qは $ \max(0, t - m_i) \leq q \leq tとなる。
/icons/hr.icon
証明
$ q = t - kと$ 0 \leq k \leq \min(t, m_i)より、$ k = t - qを不等式に代入すると、
$ 0 \leq t - q \leq \min(t, m_i)が得られる。
$ 0 \leq t - qより、$ q \leq tが得られる。
$ t - q \leq \min(t, m_i)より、$ q \geq t - \min(t, m_i)となる。
$ t \leq m_iの場合は$ t - \min(t, m_i) = 0
$ t \geq m_iの場合は$ t - \min(t,m_i) = t - m_i
これらの共通範囲を求めたいので最大値を取れば良い
したがって、$ q \geq \max(0, t - m_i)となる。
よって、$ 2つの範囲を組み合わせて$ \max(0, t - m_i) \leq q \leq tが得られた。
上記を整理すると以下のようになる。
$ {\mathrm dp}[i][j] = {\mathrm dp}[i][tw_i + p] = \max_q ( {\mathrm dp}[i - 1][qw_i + p] - qv_i) + tv_i \quad (p < w_i, \max(0, t - m_i) \leq q \leq t)
/icons/hr.icon
ここで、$ \max_q ({\mathrm dp}[i - 1][qw_i + p] - qv_i) に対して スライド最小値・スライド最大値 を使用します。（するそうです） スライド最大値はこれから勉強します。（理屈はわかるけどこの問題への適用方法がわかんない）
【ゆるぼ】スライド最大値（最小値）への理解が薄いのでおすすめの資料あれば教えていただきたいです。