[AtCoder] Educational DP Contest D – Knapsack 1

2019年11月1日

問題

方針

いわゆるナップザック問題ですね。

\( d(i, j) \) を品物 \( i \) まで調べたとき、重さの総和が \( j \) であるときの価値の総和の最大値とします。初期値は、\( d(0, 0) = 0 \) で、それ以外は \( d(i, j) = -1 \) とします。遷移は次のようになります。

• \( d(i, j) \neq -1\) のとき

品物\( i \) を持ち帰ることを考えると、

\[d(i +1, j + w[i]) = \max(d(i + 1, j + w[i]), d(i, j) + v[i])\]

となり、品物を持ち帰らないとすると、

\[d(i +1, j) = \max(d(i + 1, j), d(i, j))\]

となります。よって、答えは、\(d(N, \cdot)\) の最大値となります。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    int N, W;
    cin >> N >> W;
    ll w[N], v[N];
    for (int i = 0; i < N; i++) {
        cin >> w[i] >> v[i];
    }
    ll dp[N + 1][W + 1];
    for (int i = 0; i <=  N; i++) {
        for (int j = 0; j <= W; j++) {
            dp[i][j] = -1;
        }
    }
    dp[0][0] = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j <= W; j++) {
            int g = j + w[i];
            if (dp[i][j] == -1) continue;
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]);
            if (g > W) continue;
            dp[i + 1][g] = max(dp[i + 1][g], dp[i][j] + v[i]); 
        }
    }
    ll ans = 0;
    for (int i = 0; i <= W; i++) {
        ans = max(ans, dp[N][i]);
    }
    cout << ans << "\n";
    return 0;
}