knapsack -1

class Solution {
    public static int knapsackHelper( int[] val,int[] wt,int cap,int[][] dp,int index )
    {
        if( index < 0 || cap == 0) return 0;

        if( dp[index][cap] != -1 ) return dp[index][cap];

        int notPick = knapsackHelper( val,wt,cap,dp,index-1);

        int pick = 0;

        if( wt[index] <= cap )
        {
            pick = knapsackHelper(val,wt,cap-wt[index],dp,index-1) + val[index];
        }

        return dp[index][cap] = Math.max(pick,notPick);
    }
    static int knapsack(int W, int val[], int wt[]) {
        // code here
        int n = val.length;
        int[][] dp = new int[n+1][W+1];

        for( int i=0;i<dp.length;i++)
        {
            for( int j=0;j<dp[0].length;j++)
            {
                dp[i][j] = -1;
            }
        }

        return knapsackHelper( val,wt,W,dp,n-1);
    }
}