static int[][] dp;
    static int knapSack(int W, int wt[], int val[], int n)
    {
         dp = new int[n+1][W+1];
         for(int[] i : dp){
             Arrays.fill(i,-1);
         }
         return helper(W,wt,val,n);
    }
    static int helper(int W,int[] wt,int[] val,int n){
        if(n==0 || W==0){
             return dp[n][W] = 0;
         }
         if(dp[n][W] != -1){
             return dp[n][W];
         }
         if(wt[n-1] > W){
             return dp[n][W] = helper(W,wt,val,n-1);
         }
         return dp[n][W] =Math.max(val[n-1]+helper(W-wt[n-1],wt,val,n-1),helper(W,wt,val,n-1));
    }

//Iterative(Top-down)

static int knapSack(int W, int wt[], int val[], int n)
    {
         // your code here
         int[][] dp = new int[n+1][W+1];
         for(int i=1;i<n+1;i++){
             for(int j=1;j<W+1;j++){
                if(wt[i-1]>j){
                     dp[i][j] = dp[i-1][j];
                 }else{
                     dp[i][j] = Math.max(val[i-1] + dp[i-1][j-wt[i-1]] , dp[i-1][j]);
                 }
             }
         }
         return dp[n][W];
    }