鉄則本 A19 - Knapsack 1 (3Q, ★3)

ナップサック問題。鉄則本の問題なのでコードのみ。

• 問題へのリンク

問題概要

宝箱には 個の品物が入っている。品物 の重さは 、価値は である。

太郎君は、いくつかの品物を選んで持ち帰りたいと考えている。しかし、彼のナップザックには容量制限があるので、重さの合計が 以下になるようにする必要がある。

価値の合計としてあり得る最大の値はいくつか。

制約

• 
• 

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N, W;
    cin >> N >> W;
    vector<long long> w(N), v(N);
    for (int i = 0; i < N; i++) cin >> w[i] >> v[i];

    vector<vector<long long>> dp(N+1, vector<long long>(W+1, 0));
    for (int i = 0; i < N; i++) {
        for (int j = 0; j <= W; j++) {
            dp[i+1][j] = max(dp[i+1][j], dp[i][j]);
            if (j-w[i] >= 0) dp[i+1][j] = max(dp[i+1][j], dp[i][j-w[i]] + v[i]);
        }
    }
    cout << dp[N][W] << endl;
}