TDPC H - ナップザック

• 問題
• AC

0-basedで考える。また、$(w_i, v_i, c_i)$があらかじめ色の昇順にソートされているとする。$f(x, y, z)$を、物 $0, 1, ..., x-1$から$y$色以下、重さ$z$以下になるように選んで達成できる最大価値とすると、答えは$f(N, C, W)$である。

$f$の漸化式を考える。物$x$が色の先頭にない場合は普通のナップサック問題と同じように遷移する:

$f(0, y, z) = 0$ $f(x, y, z) = \max \begin{cases} f(x-1, y, z) & (\text{物$x-1$を入れない})\\ f(x-1, y, z-w_{x-1})+v_{x-1} & (\text{物$x-1$を入れる}) \\ \end{cases}$

物$x$がその色の先頭にある時は$x-1$から色が変わるため、新しい色を使う場合と使わない場合を比較しなければならない。$p(x)$を物$x$のひとつ前の色を持つ品物の先頭とすると、次のように書ける:

$f(x, y, z) = \max \begin{cases} f(x-1, y-1, z) & (\text{物$x-1$の色を使うが$x-1$は入れない})\\ f(x-1, y-1, z-w_{x-1})+v_{x-1} & (\text{物$x-1$の色を使い、$x-1$を入れる}) \\ f(p(x), y, z) & (\text{物$p(x)$, ..., $x-1$の色を飛ばす}) \end{cases}$

ただし、$y=0$のときはもう新しい色を使えないので$f(x,0,z) = f(p(x), 0, z)$である。計算量は${\mathcal O}(NWC)$。

---

以前に見たときは何がなんだかわからなかったが、今見たらあっさり解けた。ソートしてナップサックは典型らしい。