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

今回の問題

問題文

$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^5$
• $1 \le w_i \le W$
• $1 \le v_i \le 10^9$

自分の回答

#include <bits/stdc++.h>
#include <atcoder/dsu>
using namespace std;
using namespace atcoder;
int main() {
    string abc = "abcdefghijklmnopqrstuvwxyz";

    int n;
    cin >> n;
    int w;
    cin >> w;
    long long vlist[n];
    int wlist[n];
    for (int i = 0; i < n; i++) {
        cin >> wlist[i] >> vlist[i];
    }
    long long dp[n+1][w+1];
    for(int i = 0; i <= n; i++) {
        for(int j = 0; j <= w; j++) {
            dp[i][j] = 0;
        }
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 0; j <= w; j++) {
            if(j - wlist[i-1] >= 0) {
                dp[i][j] = max(dp[i][j], dp[i-1][j]);
                dp[i][j] = max(dp[i][j], dp[i-1][j - wlist[i-1]] + vlist[i-1]);
            } else {
                dp[i][j] = max(dp[i-1][j],dp[i][j]);
            }
        }
    }
    cout << dp[n][w] << endl;
    return 0;
}

解説

dp[i][j]をi-1個目までで重さの合計がjの時の価値の総和の最大値としてとく。
dp[i][j] = max(dp[i-1][j], dp[i-1][j - wlist[i-1]] + vlist[i-1])となることがわかる。
i個目を選ぶないときは、左のほうで選ぶときは右のほうである。今回はもらうdpで書いた。
次の問題と製薬しか違わないので要注意！（詳しい解説は次回）