ナップサック問題

問題　dpイメージ

dp[i][w] :
i 番目までの品物の中から (選ぶ、選ばない 選択)
重さが w を超えないように選んだときの、
価値の総和の最大値

// 入力
ll n, W; //荷物の数、許容容量
ll weight[110], value[110]; //重さ、価値

ll dp[110][10010]; //個数、重さ

int main() {
    cin >> n >> W;
    for (ll i = 0; i < n; ++i) cin >> value[i] >> weight[i];

    // DP初期条件: dp[0][w] = 0
    for (ll w = 0; w <= W; ++w) dp[0][w] = 0;

    // DPループ
    for (ll i = 0; i <= n; ++i) { //荷物の数
        for (ll w = 0; w <= W; ++w) { //許容容量
            if (w >= weight[i]) dp[i + 1][w] = max(dp[i][w - weight[i]] + value[i], dp[i][w]);
            else dp[i + 1][w] = dp[i][w]; //最初のみ使用
        }
    }

    cout << dp[n][W] << endl; //n以下 W以下 の最大値
}