[AtCoder] Educational DP Contest E – Knapsack 2

2019年11月2日

問題

方針

商品の重さの最大値が \( 10^9\) なので、添え字で重さを管理して考えるのはメモリ的にきついので、別の方法を考えます。価値を添え字で管理することを考えます。\( d(i, j)\) を商品 \( i \) まで調べたとき、価値の総和が \( j \) であるときのナップザックの重さとします。初期値は、\( d(0, 0) = 0\) でそれ以外は、\( d(i, j) = \infty \) とします。 また、価値の総和の最大値は \( 10^5 \) であることに注意します。この配列の更新式は、

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

\[
\begin{eqnarray}
d(i + 1, j) &=& \min(d(i, j) , d(i + 1, j))\\
d(i + 1, j + v_i) &=& min(d(i + 1, j + v_i), d(i, j) + w_i)
\end{eqnarray}
\]

となります。答えは、\(d[N][i] \leq W \) を満たす最大の \( i \) となります。また、\( d(i, j) + w_i > W\) となる商品 \( i \) は考慮しなくてよいので、更新時に省きます。

コード

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

    return 0;
}