Spoj KNAPSACK Solution

The Knapsack Problem

#include<bits/stdc++.h>

#define ll long long

#define fastio ios_base :: sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

using namespace std;

ll knapsack(int weight, int sz[], int val[], int n)

{

    ll k[n+1][weight+1];

    for(int i=0; i<=n; i++)

    {

        for(int j=0; j<=weight; j++)

        {

            if(i == 0 || j == 0)

                k[i][j] = 0;

            else if(sz[i-1] <= j)

                k[i][j] = max( (val[i-1] + k[i-1][j - sz[i-1]]) , k[i-1][j]);

            else

                k[i][j] = k[i-1][j];

        }

    }

    return k[n][weight];

}

int main()

{

    fastio

    

    int weight, n;

    cin >> weight >> n;

    int sz[n], val[n];

    for(int i=0; i<n; i++)

        cin >> sz[i] >> val[i];

    cout << knapsack(weight, sz, val, n) << "\n";

    return 0;

}