Add Memoization solution for knapsack (TheAlgorithms#2560)

921vikram · Vikram Prakash · web-flow · commit bb9e8654b51f · 2021-10-14T14:13:45.000+03:00
Co-authored-by: Vikram Prakash &lt;vpsahu@juniper.net&gt;
diff --git a/DynamicProgramming/KnapsackMemoization.java b/DynamicProgramming/KnapsackMemoization.java
@@ -0,0 +1,53 @@
+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);
+  }
+}
