package DynamicProgramming;


import java.util.Arrays;

/**
 * Recursive Solution for 0-1 knapsack with memoization
 */
public class KnapsackMemoization {

 private static int[][] t;


 // Returns the maximum value that can
 // be put in a knapsack of capacity W
 public static int knapsack(int[] wt, int[] value, int W, int n) {
 if(t[n][W] != -1) {
 return t[n][W];
 }
 if (n == 0 || W == 0) {
 return 0;
 }
 if (wt[n - 1] <= W) {
 t[n-1][W-wt[n-1]] = knapsack(wt, value, W - wt[n - 1], n - 1);
 // Include item in the bag. In that case add the value of the item and call for the remaining items
 int tmp1 = value[n - 1] + t[n-1][W-wt[n-1]];
 // Don't include the nth item in the bag anl call for remaining item without reducing the weight
 int tmp2 = knapsack(wt, value, W, n - 1);
 t[n-1][W] = tmp2;
 // include the larger one
 int tmp = tmp1 > tmp2 ? tmp1 : tmp2;
 t[n][W] = tmp;
 return tmp;
 // If Weight for the item is more than the desired weight then don't include it
 // Call for rest of the n-1 items
 } else if (wt[n - 1] > W) {
 t[n][W] = knapsack(wt, value, W, n - 1);
 return t[n][W];
 }
 return -1;
 }

 // Driver code
 public static void main(String args[]) {
 int[] wt = {1, 3, 4, 5};
 int[] value = {1, 4, 5, 7};
 int W = 10;
 t = new int[wt.length+1][W+1];
 Arrays.stream(t).forEach(a -> Arrays.fill(a, -1));
 int res = knapsack(wt, value, W, wt.length);
 System.out.println("Maximum knapsack value " + res);
 }
}