Typical DP Contest H - ナップザック

http://tdpc.contest.atcoder.jp/tasks/tdpc_knapsack

問題概要

N個のものがあって、それぞれに重さw・価値v・色cが設定されている。重さ合計の最大値Wと使える色の種類の最大値Cが与えられるので、その範囲内で価値の合計が最も高くなるような組合せを選んだときの価値の最大値を求めよ。

N <= 100

W <= 10000

C <= 50

解法

普通にDPをやろうとすると「重さ」と「使った色の種類」を状態に取ってやることになるが、これだと状態数がO(W2C)、遷移がO(NW2C)になって全然間に合わない。

まず必要なのは各色ごと別個にDPを行うことである。つまり色の条件を無視して重さだけで普通のナップザック問題を解くようなDPをやる。これである一色について各重さごとの価値を出すことができる(=ひとつひとつのものを個別にみる必要がなくなり、色単位で考えていくことができるようになる)。

次に(使った色数、重さ)を状態にしてまたDPをやる。色を順番に舐めながら、i色目を使う時には0~(i-1)色目のDPに対して更新をかけ、使った色が一色増えたという扱いにすればよい。以上でC色まで使ったときの重さW以下の最大値が出せる。

最初のDPがO(NWC), 次のDPが(WC2)で十分間に合う。

感想

自力では解けず。2NをN2に落とすというところを考えると典型といえる……のか???

コード (D言語)

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop;

void main() {
    auto s = readln.split.map!(to!int);
    auto N = s[0], W = s[1], C = s[2];
    auto WV = new Tuple!(int, int)[][](55);
    foreach (i; 0..N) {
        s = readln.split.map!(to!int);
        WV[s[2]] ~= tuple(s[0], s[1]);
    }


    auto dp = new int[][](55, 10101);

    foreach (c; 1..55) {
        foreach (c2; iota(c-1, -1, -1)) {
            auto tmp = dp[c2].dup;

            foreach (wv; WV[c]) {
                int w = wv[0], v = wv[1];
                foreach (i; iota(10100, -1, -1))
                    if (tmp[i] > 0 && i + w <= W)
                        tmp[i+w] = max(tmp[i+w], tmp[i] + v);
                if (w <= W)
                    tmp[w] = max(tmp[w], v);
            }

            foreach (i; 0..10101)
                dp[c2+1][i] = max(dp[c2+1][i], tmp[i]);
        }
    }

    dp[C][0..W+1].reduce!max.writeln;
}