0-1 Knapsack(DP)

#include<bits/stdc++.h>

using namespace std;

int knapsack(int W, int v[], int wt[], int n)

{

    int i, j;

    int k[n+1][W+1];

    

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

    {

        for(j=0; j<=W; j++)

        {

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

                k[i][j] = 0;

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

                k[i][j] = max((v[i-1]+k[i-1][j-wt[i-1]]), k[i-1][j]);

            else

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

        }

    }

    

    return k[n][W];

}

int main()

{

    int n, i, value, weight, W;

    

    cout << "Enter Size :: ";

    cin >> n;

    

    int v[n], wt[n];

    

    cout << "Enter Value and Weight :: " << endl;

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

    {

        cin >> value >> weight;

        v[i] = value;

        wt[i] = weight;

    }

    

    cout << "Enter Weight :: ";

    cin >> W;

    

    int p = knapsack(W, v, wt, n);

    

    cout << "Value :: " << p << endl;

    

    return 0;

}