E - Knapsack 2

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