TDPC H - ナップザック

考え方

特殊なナップサック問題。
基本的なナップサック問題については、「ナップサック問題」の記事参照。

今回の特殊な点は、色数が指定数以下でなくてはならない点。
そこで、DPテーブルは、色数も持たせて通常より $1$ 次元多くする。

そして、更新は、同じ色の荷物をまとめて扱う。
例えば、色 $5$ であるグループを反映する場合、仮に指定色数が $3$ だとして、以下のようにする。

まず、色数が $2$ 以下である部分をDPテーブルからコピーする。
それを通常ナップサック問題のインプレース更新と同じ要領で、色 $5$ である荷物全てについて処理する。
その後、色数が $3$ 以下である部分に対し、今求めた各重さでの最大価値が大きければ更新する。
これを、色数 $1$ 以下から色数 $2$ 以下へ、色数 $0$ 以下から色数 $1$ 以下へも行う。

これを全ての色について処理すれば、答えが出る。

計算量は $O(NKW)$。

入力例1での動作

入力を受け取る。
以下では、重量制限を m、色数制限を k とする。

n: 4
m: 5
k: 2
w: {1, 1, 1, 10}
v: {10, 20, 30, 100}
c: {1, 2, 3, 4}

まず、荷物を色ごとに分ける。

色1: {(1, 10)}
色2: {(1, 20)}
色3: {(1, 30)}
色4: {(10, 100)}

dp[i][j] を、$i$ 色以内、重さ $j$ 以下で選んだときの最大価値とする。

色 $1$ の荷物を処理すると、DP テーブルは次のようになる。

色 $2$ の荷物まで処理すると、次のようになる。

色 $3$ の荷物まで処理すると、次のようになる。

色 $4$ の荷物は重さが $10$ なので、重量制限 $5$ の範囲では追加できず、DP テーブルは変化しない。

最終的に dp[2][5] = 50 となるので、答えは $50$。

注意点

特になし。

別解

特になし。