0-1 knapsack(recursively)

#include<bits/stdc++.h>

#define sz 1001

#define N 100005

using namespace std;

int v[sz], w[sz], n;

int num[sz][N];

int knapsack(int i, int wt)

{

    if(wt < 0)

        return INT_MIN;

    if(i == n || wt == 0)

        return 0;

    if(num[i][wt] != INT_MIN)

        return num[i][wt];

    int ans1 = knapsack(i+1, wt - w[i]) + v[i];

    int ans2 = knapsack(i+1, wt);

    num[i][wt] = max(ans1, ans2);

    return num[i][wt];

}

int main()

{

    cout << "Enter a Number :: ";

    cin >> n;

    cout << "Enter Value and Weight :: \n";

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

        cin >> v[i] >> w[i];

    int target;

    cout << "Enter Total Weight :: ";

    cin >> target;

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

    {

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

            num[i][j] = INT_MIN;

    }

    int r = knapsack(0, target);

    cout << "Maximum Profit :: " << r << "\n";

    return 0;

}