mayoko’s diary

プロコンとかいろいろ。

AtCoder Beginner Contest 032 D - ナップサック問題

ナップサック問題か〜どのナップサックかな〜 多分半分全列挙?」「全部です」「はい」

解法

蟻本に載ってるナップサック問題の解法を試せば良いです。蟻本第二版での話ですが,

半分全列挙 -> p148
w[i] <= 1000 (一番シンプルなやつ) -> p52
v[i] <= 1000 -> p60

に書いてあります。

ll v[222], w[222];
pll ps[1<<16];
ll dp[2][222*1000];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    ll W;
    cin >> N >> W;
    for (int i = 0; i < N; i++) cin >> v[i] >> w[i];
    if (N <= 30) {
        int n = N/2;
        for (int i = 0; i < 1<<n; i++) {
            ll sw = 0, sv = 0;
            for (int j = 0; j < n; j++) {
                if ((i>>j)&1) {
                    sw += w[j];
                    sv += v[j];
                }
            }
            ps[i] = pll(sw, sv);
        }
        sort(ps, ps+(1<<n));
        int m = 1;
        for (int i = 1; i < 1<<n; i++) {
            if (ps[m-1].second < ps[i].second) ps[m++] = ps[i];
        }
        ll res = 0;
        for (int i = 0; i < 1<<(N-n); i++) {
            ll sw = 0, sv = 0;
            for (int j = 0; j < N-n; j++) {
                if ((i>>j)&1) {
                    sw += w[n+j];
                    sv += v[n+j];
                }
            }
            if (sw <= W) {
                ll tv = (lower_bound(ps, ps+m, make_pair(W-sw, 1ll<<55))-1)->second;
                res = max(res, sv+tv);
            }
        }
        cout << res << endl;
        return 0;
    }
    bool flag = true;
    for (int i = 0; i < N; i++) flag &= w[i] <= 1000;
    memset(dp, -1, sizeof(dp));
    dp[0][0] = 0;
    if (flag) {
        for (int i = 0; i < N; i++) {
            int cur = i%2, tar = cur^1;
            for (int j = 0; j <= i*1010; j++) dp[tar][j] = -1;
            for (int j = 0; j <= i*1010; j++) {
                if (dp[cur][j] == -1) continue;
                dp[tar][j] = max(dp[tar][j], dp[cur][j]);
                dp[tar][j+w[i]] = max(dp[tar][j+w[i]], dp[cur][j]+v[i]);
            }
        }
        ll ans = 0;
        for (int i = 0; i < 222*1000 && i <= W; i++) {
            ans = max(ans, dp[N%2][i]);
        }
        cout << ans << endl;
    } else {
        for (int i = 0; i < N; i++) {
            int cur = i%2, tar = cur^1;
            for (int j = 0; j <= i*1010; j++) dp[tar][j] = -1;
            for (int j = 0; j <= i*1010; j++) {
                if (dp[cur][j] == -1) continue;
                if (dp[tar][j] == -1 || dp[tar][j] > dp[cur][j]) dp[tar][j] = dp[cur][j];
                if (dp[tar][j+v[i]] == -1 || dp[tar][j+v[i]] > dp[cur][j] + w[i]) dp[tar][j+v[i]] = dp[cur][j]+w[i];
            }
        }
        ll ans = 0;
        for (int i = 0; i < 222*1000; i++) {
            if (dp[N%2][i] != -1 && dp[N%2][i] <= W) ans = i;
        }
        cout << ans << endl;
    }
    return 0;
}