Typical DP Contest H - ナップザック

問題概要

$N (\leq 100)$ 個の物があり，$i$ 番目の物の重さ，価値，色は $ w_i, v_i, c_i$ である。重さ $W$，かつ $C$ 色までナップザックに詰めることができるとき，ナップザックに詰められた物の価値の和の最大値を求めよ。

解法概要

解法の前に，私が陥った WA 解法 (ソースコード) について書いておきたい。

$\mathit{dp}_{i, j}$ を，$i$ 色使用済みで重さがの和が $j$ の場合の価値の和の最大値とする。あとは通常のナップザック問題と同じように $N$ 個の物を順番に見る。ただし，$\mathit{color}_{i, j}$ を$\mathit{dp}_{i, j}$ で使用済みの色の集合と考えて $\mathit{dp}_{i, j}$ と同時に更新していく。

この場合，次のようなケースで WA となってしまう。

6 つの物のうち 3 つめまで見た場合を考えてみよう。同じ「2 色使用済み，重さは 2」であれば，1 番目と 2 番目を入れる場合，2 番目と 3 番目を入れる場合，1 番目と 3 番目を入れる場合の 3 通りが考えられる。この WA 解法では色数と重さが同じであれば中身の色が何であるかを区別しない。そのため，全体を見たときに色 2 と色 3 を入れるのが最適 (価値の合計を 12 にすることができる) であることを判定できず，3 番目まで見た地点で価値が大きい色 1 と色 3 を入れる (価値の合計は 11 にしかならない) を入れてしまう。

ではどうすれば良いのかというと，すごくざっくりいうとある色 $c$ の全体に対する影響をまとめて計算して，色 $c$ の影響分を dp テーブルにまとめて足し合わせることができれば良い。

具体的な実現方法を述べる。$\mathit{dp}_{i, j}$ の定義は WA 解放と同じである。ただし，色ごとに，その地点での dp テーブルのコピー($dpk$ とする)を用意し，それを使って通常のナップザック問題のような状態遷移を行う。色ごとにまとめて $\mathit{dpk}$ を考えているので，色数は$\mathit{dp}_{i, j}$ から 1 だけ増える。そのため，ナップザック問題の要領で重さと価値の計算をしているときには色数 $i$ の遷移は考えなくてよい。こうしてできた $\mathit{dpk}$ は $\mathit{dp}$ が今見ている色 $k$ の影響を受けると仮定した場合の途中計算結果である。これを使って，すべての $i, j$ について $\mathit{dp}_{i, j}$ を $\mathit{dp}_{i, j}$ か $\mathit{dpk}_{i-1, j}$ のうち大きい方に更新する (色数 $i-1$ の状態に色 $k$ を追加したら色数は $i$ になるはず)。

ソースコード

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <utility>

using namespace std;

constexpr int NC = 50;

int main() {
    int N, W, C;
    cin >> N >> W >> C;
    int w, v, c;
    vector<Pii> items[NC+1];
    for(int k=0;k<N;++k) {
        cin >> w >> v >> c;
        items[c].emplace_back(w, v);
    }

    vector<vector<int>> dp(C+1, vector<int>(W+1, -1));
    dp[0][0] = 0;
    for(int ci=1;ci<=NC;++ci) {
        vector<vector<int>> dpk(dp);
        for(int k=items[ci].size()-1;k>=0;--k) {
            for(int i=C-1;i>=0;--i) {
                for(int j=W-items[ci][k].first;j>=0;--j) {
                    dpk[i][j+items[ci][k].first] = max(dpk[i][j+items[ci][k].first], dpk[i][j] + items[ci][k].second);
                }
            }
        }
        for(int i=0;i<C;++i) {
            for(int j=0;j<=W;++j) {
                dp[i+1][j] = max(dp[i+1][j], dpk[i][j]);
            }
        }
    }

    int ans = 0;
    for(int i=0;i<=C;++i) {
        for(int j=0;j<=W;++j) ans = max(ans, dp[i][j]);
    }

    cout << ans << endl;
}

所感

以前挫折した Typical DP Contest を埋めてみることにした。