Typical DP Contest H - ナップザック
問題
n個の品物があり、i番目の品物は重さがwi, 色がci, 価値がviである。
ナップサックに重さの合計がW以下, 色の合計がC色以下であるように品物を詰める。
価値の最大はいくつか。
制約条件
n≦100
W≦10000
C≦50
方針
品物を色ごとにまとめる。
色ごとに、
dp[1回以上何かの品物を使ったか][今までの色の合計][重さの合計]
を更新する(普通のナップサック問題的な)DPをして、
一つの色が終わったら、そのつど
dp[0][i][j]にdp[0][i][j]とdp[1][i][j]をまとめる。
ソースコード
int n, W, C, dp[2][51][100010]; map<int, vector<pi> > m; int main(){ cin >> n >> W >> C; rep(i, n){ int w, c, v; cin >> w >> v >> c; m[c].pb(mp(w, v)); } int i = 0, ans = 0; each(it, m){ memset(dp[1], -1, sizeof(dp[1])); each(j, it->second) for(int l = W; l >= 0; l--) for(int k = C; k >= 0; k--) rep(u, 2){ if(l + j->first > W || k + !u > C || dp[u][k][l] < 0) continue; dp[1][k + !u][l + j->first] = max(dp[1][k + !u][l + j->first], dp[u][k][l] + j->second); ans = max(ans, dp[1][k + !u][l + j->first]); } rep(j, C+1) rep(k, W+1) dp[0][j][k] = max(dp[0][j][k], dp[1][j][k]); } cout << ans << endl; return 0; }