Typical DP Contest H - ナップザック

• 問題

問題概要

N個の荷物の重さwi,価値vi,色ciが与えられる.
重さW以下,色C色以下で達成できる最大価値を求めよ.
1 <= N <= 100,1 <= W <= 10⁵, 1 <= C <= 50

解法

dp(i,j) := (i色以下,重さj以下で持てる最大価値) としてdp(i,j)を更新していく.
w,vは色ごとに持っておいて,各色でその色を使う時を考えていくが,
色c を見ている時,各cについてdp(i,j) の更新のために
dp2(i,j) := (c以下の色をi色以下使った時の重さj以下の最大価値) を用意する.
するとある色cの荷物w,vを見る時に各i,jについて以下の3つを遷移すれば良い.
dp2(i+1,j) = max(dp2(i+1,j), dp2(i+1,j-w)+v, dp(i,j-w)+v ) .. ( * )
前から 荷物を持たない場合,荷物を持ちその色の荷物を既に持っていた場合,荷物を持ちその色の荷物を初めて持つ場合となる.
なおjは逆順に遷移する.これは昇順に遷移すると,j->j+w->j+2wと更新され,荷物が無限個あることになってしまうからである.
上の式を更新し終わったら i,jについて dp(i,j) = max(dp(i,j),dp2(i,j)) としてdpテーブルを更新する.
ここでわざわざdpとdp2を分けるのは ( * ) の処理の時にdp(i,j)が色c-1以下だけを使ったテーブルである必要があるためである.
計算量は O(N C² W)となって十分.

メモ

最初各色についてDPしようとしたらO(NCW²)となって無理だった.難しい.

コード