public class ZeroOneKnapsack {
    public static int zerOneKnapsack(int[] val, int[] wt, int w, int i){
        if(w==0 || i==0) return 0;
        if(wt[i-1]<=w){
            int ans1= val[i-1]+zerOneKnapsack(val,wt,w-wt[i-1],i-1);
            int ans2= zerOneKnapsack(val,wt,w,i-1);
            return Math.max(ans1,ans2);
        }
        else return zerOneKnapsack(val,wt,w,i-1);
    }

    public static int memoZerOneKnapsack(int[] val, int[]wt, int w,int i, int[][] arr){
        if(w==0 || i==0){
            return 0;
        }
        if(arr[i][w]!=-1){
            return arr[i][w];
        }
        if(wt[i-1]<=w){
            int ans1= val[i-1]+memoZerOneKnapsack(val,wt,w-wt[i-1],i-1,arr);
            int ans2= memoZerOneKnapsack(val,wt,w,i-1,arr);
            arr[i][w]= Math.max(ans1,ans2);
        }
        else {
           arr[i][w]= memoZerOneKnapsack(val, wt, w, i - 1, arr);
        }
        return arr[i][w];
    }//all elements of table must be initialised with -1's.

    public static int tabZeroOneKnapsack(int[] val, int[] wt, int w){
        int n= val.length;
        int[][] dp =new int[n+1][w+1];
        for (int i = 0; i < n+1; i++) dp[i][0]=0;
        for(int i=0;i<w+1;i++) dp[0][i]=0;
        for (int i = 1; i < n+1; i++) {
            for (int j = 1; j < w+1; j++) {
                int v=val[i-1];
                int weight=wt[i-1];
                if(weight<=j){
                    int incProfit=v+dp[i-1][j-weight];
                    int excProfit=dp[i-1][j];
                    dp[i][j]=Math.max(incProfit,excProfit);
                } else{
                    dp[i][j]=dp[i-1][weight];
                }
            }
        }
        return dp[n][w];
    }

    public static void main(String[] args){
        int[] val={15,14,10,45,30};
        int[] wt={2,5,1,3,4};
        int w=7;
        System.out.println(zerOneKnapsack(val,wt,w,val.length));
        int[][] arr=new int[val.length+1][w+1]; // for memoZeroKnapsack
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[0].length; j++) {
                arr[i][j]=-1;
            }
        }
        System.out.println(memoZerOneKnapsack(val,wt,w,val.length,arr));
    }
}