AtCoder Educational DP Contest E問題解いてみた

今回の問題

問題文

$N$ 個の品物があります。品物には $1, 2, \dots, N$ と番号が振られています。
各 $i$ $(1 \le i \le N)$ について、品物 $i$ の重さは $w_i$ で、価値は $v_i$ です。

太郎君は、$N$ 個の品物のうちいくつかを選び、ナップサックに入れて持ち帰ることにしました。
ナップサックの容量は $W$ であり、持ち帰る品物の重さの総和は $W$ 以下でなければなりません。

太郎君が持ち帰る品物の価値の総和の最大値を求めてください。

制約

• 入力はすべて整数である。
• $1 \le N \le 100$
• $1 \le W \le 10^9$
• $1 \le w_i \le W$
• $1 \le v_i \le 10^3$

自分の回答

#include <bits/stdc++.h>
#include <atcoder/dsu>
using namespace std;
using namespace atcoder;
int main() {
    int n;
    cin >> n;
    int w;
    cin >> w;
    int vlist[n];
    long long wlist[n];
    for (int i = 0; i < n; i++) {
        cin >> wlist[i] >> vlist[i];
    }
    long long dp[n+1][n*1000+1];
    for(int i = 0; i <= n; i++) {
        for(int j = 0; j <= n*1000; j++) {
            dp[i][j] = 1e15;
        }
    }
    dp[0][0] = 0;
    for(int i = 1; i <= n; i++) {
        for(int j = 0; j <= n*1000; j++) {
            if(j - vlist[i-1] >= 0) {
                dp[i][j] = min(dp[i-1][j], dp[i-1][j - vlist[i-1]] + wlist[i-1]);
            } else {
                dp[i][j] = min(dp[i-1][j],dp[i][j]);
            }
        }
    }
    long long ans = 0;
    for(long long j = 0; j <= n*1000; j++) {
        if(dp[n][j] <= w) {
            ans = j;
        }
    }
    cout << ans << endl;
    return 0;
}

解説

前回の問題とほとんど変わらないが制約だけ変わっている。さっきの方法で解こうとすると、wが大きすぎるので、メモリも時間も足りない。そこで今回はvが小さいことに注目してとく。
dp[i][j]をi-1個目まで考えた時、価値の合計がjとなる重さの合計の最小値とする。
dp[i][j] = min(dp[i-1][j], dp[i-1][j - vlist[i-1]] + wlist[i-1])となることがわかる。今回はもらうdpで書いた。