D - Knapsack 1

    1#include <bits/stdc++.h>
    2 
    3using namespace std;
    4 
    5typedef long long ll;
    6 
    7int main(){
    8    ios::sync_with_stdio(0);
    9    cin.tie(0);
    10    int n, w;
    11    cin >> n >> w;
    12    vector<ll> wt(n), val(n);
    13    for(int i = 0; i < n; i++){
    14        cin >> wt[i]; cin >> val[i];
    15    }
    16    vector<vector<ll>> dp(wt.size() + 1, vector<ll>(w + 1));
    17    for(int i = 0; i <= wt.size(); i++){
    18        for(int j = 0; j <= w; j++){
    19            if(j == 0 || i == 0) dp[i][j] = 0;
    20            else {
    21                ll pick = 0;
    22                if(wt[i - 1] <= j){
    23                    pick = max(dp[i][j], dp[i - 1][j - wt[i - 1]] + val[i - 1]);
    24                }
    25                ll not_pick = dp[i - 1][j];
    26                dp[i][j] = max(pick, not_pick);
    27            }
    28        }
    29    }
    30    cout << dp[wt.size()][w] << '\n';
    31}