knapsack (Tabulation)

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

#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define ll long long
#define ull unsigned long long
#define MOD 1000000007
#define PI 3.14159265
#define ceil(a, b) ((a / b) + (a % b ? 1 : 0))
#define imin INT_MIN
#define imax INT_MAX
#define nl '\n'

void Start_Crushing(){
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
 #ifndef ONLINE_JUDGE
     freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
     freopen("error.txt", "w", stderr);
 #endif
}
vector<int> weights, values;
int n, w;

int knapsack(){
    int grid[n + 1][w + 1];

    for(int i = 0; i <= n; i++){
        for(int j = 0; j <= w; j++){
            if(!i or !j)
                grid[i][j] = 0;
            else if(weights[i - 1] <= j)
                grid[i][j] = max(grid[i - 1][j], values[i - 1] + grid[i - 1][j - weights[i - 1]]);
            else
                grid[i][j] = grid[i - 1][j];
        }
    }

    return grid[n][w];
}

void solve(){
    cin >> n >> w;
    weights.resize(n), values.resize(n);

    for(int i = 0; i < n; i++){
        cin >> weights[i] >> values[i];
    }
    cout << knapsack();
}

int main(){
    Start_Crushing();

    int t = 1;
    /*is Single Test case?*/ //cin >> t;
    while (t--) {
        solve();
        if(!t) break;
        cout << "\n";
    }

     cerr << "time taken : " << (float)clock() / CLOCKS_PER_SEC << " secs" << endl;

    return 0;
}