AtCoder Typical DP Contest H ナップザック : Grenache's blog

問題概要

問題文はこちらを参照してください。

ナップサック問題の変形です。

解法

ナップサック問題の変形というと、個数制限なしのナップサック問題(参考書籍の蟻本に出てきます)などが典型かと思いますが、漸化式の変更をする必要がありました。

この問題も色というちょっとした制限の追加だけで、解けそうで解けなくなってしまいます。ただ、ＤＰに慣れてくると$i$番目までのもので使った色の種類が$c$以下となり重さの合計が$w$以下というまとめ方になるんだろうなというのはわかってくると思います。これをどう実装するかが難しいんですけど。。。

通常のナップサック問題では$i$番目のものまでを使ってと考える時に、$i-1$番目までのものにしか依存しないので、実際には$dp[W]$という1次元の記憶領域しか必要としません。今回も、何番目までのものを使ったのかは領域を使いまわせると仮定して、$i$種類以下の色を使って、重さの合計が$j$以下の時の価値の最大値を$dp[i][j]$で表すと考えてみます。もし、これが求められたら、答えは$dp[C][W]$になります。

これをどうやって求めるかですが、それまで使ったことがない色のものを考える時に、$i\lt C$の$dp[i][j]$を使って、通常のＤＰを行うと$C$種類以下の色のものでの最大価値が求まります。ただ、新しく考えるものの色をすでに使ったことがある場合は、$i\le C$の$dp[i][j]$を使ってＤＰを行う必要があります。これを実現するために2つの漸化式をたてます。

漸化式の定義： $$\begin{eqnarray} dp2[i][j] & = & \max\{ dp2[i][j],\\ & & dp[i-1][j - w_k]+v_k,\\ & & dp2[i][j - w_k]+v_k\} \end{eqnarray}$$ $$dp[i][j] = \max\{dp[i][j],\ dp2[i][j]\}$$

$dp[i][j]$：$i$種類以下の色のものを使って、合計の重さ$j$以下となる組合せでの価値の合計の最大値

$dp2[i][j]$：$dp[i][j]$で使ってない色のものを組合せとして考える場合に、その新色を含めて$i$種類以下の色のものを使って、合計の重さ$j$以下となる組合せでの価値の合計の最大値

$k$：$k\in\{dp[i][j]に含まれていない色c_lのものの集合\}$
$(0\le i \lt C,\ 0\le j \le W)$

初期値：全て$0$

求める解：$dp[C][W]$

この2つの漸化式は、次の手順で計算をしていきます。

色が$c_l$のものについて$dp2$を更新する(この時$j$は$W$から減らす方向でループを回す)。
$dp$を更新する
次のまだ使っていないものの色について1.から繰り返す。

このような手順を踏むことで、1.が終わった時点では色が$c_l$のものを使いかつ$C$種類以下のものの組み合わせでの価値の合計の最大値が$dp2$に入っています。それを2.によって$dp$とマージすることで、$dp$に(どの色の組み合わせかは問わずに)$C$種類以下のものの組み合わせでの価値の合計の最大値が入っています。