Typical DP Contest H - ナップザック

解法

基本的な考え方は普段のナップサックと同じで、ある重さになるような荷物の選び方の中での価値の最大値、を求めていきます。
今回、荷物には色が塗られており、 $C$ 種類以下でナップサックに荷物をつめなければなりません。
ということで、次のようなDPを考えます。
$dp[j][k][l][m] =$ 色を $k$ 種類使用して、重さの合計が $j$ になるような荷物の選び方の中での価値の総和の最大値
ここで、 $l,m$ が何を表しているかというと、 $l$ は次に見る荷物 $i$ の色 $c_i$ を $i-1$ までの荷物を調べた段階で使用しているかどうか、そして $m$ は $i$ の荷物をすでに使用したかどうか、です。
$l$ が存在することで、全ての荷物を色の番号順でソートしておけば、同じ色を違う種類と判定することなく調べることができ、 $m$ が存在することで、荷物 $i$ を2つ以上いれる心配がなくなります。
ということで、あらかじめ全ての荷物を、色の番号が若い順にソートしておきます。

さて、荷物 $i$ に注目ときのDPの遷移を考えていきます。
まず、DPテーブルの整理から始めます。というのも、 $i$ 番目の荷物を調べる時も、 $i-1$ 番目の荷物を調べる時も、同じDPテーブルを再利用するためです。
2つのパターンが存在します。荷物 $i$ の色 $c_i$ が、それ以前に登場しているかどうか、です。あらかじめソートをしているので、1つ前の荷物の色と比較して、違ったならば色 $c_i$ は $i$ 番目で初出、等しければそれ以前ですでに使用していることになります。

$c_i$ が $i$ 番目で初出ではない場合 $( c_{i-1} = c_i)$
$i-1$ 番目の荷物について調べた際の、 $m$ 、すなわち $i-1$ 番目の荷物を使用しているかどうか、という情報はもう必要ないので、 $m=0$ にまとめ上げます。ということで、
$dp[j][k][l][0] = max(dp[j][k][l][0],dp[j][k][l][1])$
という処理と、
$dp[j][k][l][1] = 0$
という操作をしてあげます。
$c_i$ が $i$ 番目で初出だった場合 $( c_{i-1} \neq c_i)$
上の操作に加えて、 $l$ のリセットも必要になります。 $i-1$ 番目までの荷物の組み合わせで、色 $c_i$ の荷物を使用することがないからです。
$dp[j][k][0][0] = max(dp[j][k][l][m])$
です。それ以外は0で初期化するので、
$dp[j][k][0][1] = dp[j][k][1][0] = dp[j][k][1][1] = 0$
という処理をしてあげます。

さて、DPテーブルの整理が終わったので、 $i$ 番目の荷物について考えていきます。
$i$ 番目の荷物を使用しておらず、かつ

それまでで色 $c_i$ の荷物を使用していなければ、色の種類数に+1
色 $c_i$ の荷物を使用していれば、色の種類数はそのまま

となるので、DPの遷移は次のようになります。 $i$ を使用した時点で、 $l,m$ はどちらも1になることに注意します。
$dp[j][k][1][1] = max(dp[j][k][1][1] ,dp[j- w_i][k-1][0][0]+v_i,dp[j-w_i][k][1][0]+v_i)$
ということで、この更新を行いつつ、 $dp[j][k][1][1]$ の更新を行うごとに、全体での最大値を更新していけば、この遷移が終えた段階で、更新した最大値が答えとなります。

ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

Typical DP Contest H - ナップザック

解法