0-1 Knapsack (Dynamic Programming)

#include<bits/stdc++.h>
using namespace std;
int knapsack(int n,int v[],int w[],int W,int **dp){
    if(n<=0 || W<=0)
        return 0;
    if(dp[n][W]!=-1)
        return dp[n][W];
    if(w[n-1]>W)
        {
        dp[n][W]=knapsack(n-1,v,w,W,dp);
        return dp[n][W];
    }
    else{
        dp[n][W]=max(knapsack(n-1,v,w,W-w[n-1],dp)+v[n-1],knapsack(n-1,v,w,W,dp));
        return dp[n][W];	
    }
}

int main(){
    // write your code here
    int n;
    cin>>n;
    int v[n],w[n];
    for(int i=0;i<n;i++){
        cin>>w[i];
    }
    for(int i=0;i<n;i++){
        cin>>v[i];
    }
    
    int W;
    cin>>W;
    int **dp=new int*[n+1];
    for(int i=0;i<=n;i++){
        dp[i]=new int[W+1];
    }
    for (int i = 0; i <= n; i++)
        for (int j = 0; j < W + 1; j++)
            dp[i][j] = -1;
    int ans=knapsack(n,v,w,W,dp);
    cout<<ans<<endl;
    return 0;

}