Repository: TheAlgorithms/Java
Pull request #3769 (2022-11-19 05:25:13)

KnapsackMemoization already Exist
https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/dynamicprogramming/KnapsackMemoization.java  
Here is the one.




debasishbsws: I should add some Tests.

Patch:
diff --git a/DIRECTORY.md b/DIRECTORY.md
index e557e92b..983c6b48 100644
--- a/DIRECTORY.md
+++ b/DIRECTORY.md
@@ -211,7 +211,6 @@
             * [LongestValidParentheses](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/dynamicprogramming/LongestValidParentheses.java)
             * [MatrixChainMultiplication](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/dynamicprogramming/MatrixChainMultiplication.java)
             * [MatrixChainRecursiveTopDownMemoisation](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/dynamicprogramming/MatrixChainRecursiveTopDownMemoisation.java)
-            * [MemoizationTechniqueKnapsack](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/dynamicprogramming/MemoizationTechniqueKnapsack.java)
             * [MinimumPathSum](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/dynamicprogramming/MinimumPathSum.java)
             * [MinimumSumPartition](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/dynamicprogramming/MinimumSumPartition.java)
             * [NewManShanksPrime](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/dynamicprogramming/NewManShanksPrime.java)
@@ -307,6 +306,7 @@
             * [ReverseNumber](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/maths/ReverseNumber.java)
             * [RomanNumeralUtil](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/maths/RomanNumeralUtil.java)
             * [SimpsonIntegration](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/maths/SimpsonIntegration.java)
+            * [SquareFreeInteger](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/maths/SquareFreeInteger.java)
             * [SquareRootWithBabylonianMethod](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/maths/SquareRootWithBabylonianMethod.java)
             * [SquareRootWithNewtonRaphsonMethod](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/maths/SquareRootWithNewtonRaphsonMethod.java)
             * [StandardDeviation](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/maths/StandardDeviation.java)
@@ -347,6 +347,7 @@
             * [CountChar](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/others/CountChar.java)
             * [countSetBits](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/others/countSetBits.java)
             * [CountWords](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/others/CountWords.java)
+            * [CRC16](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/others/CRC16.java)
             * [CRC32](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/others/CRC32.java)
             * [CRCAlgorithm](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/others/CRCAlgorithm.java)
             * [Damm](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/others/Damm.java)
@@ -418,6 +419,7 @@
             * [UnionFind](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/searches/UnionFind.java)
             * [UpperBound](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/searches/UpperBound.java)
           * sorts
+            * [BeadSort](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/sorts/BeadSort.java)
             * [BinaryInsertionSort](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/sorts/BinaryInsertionSort.java)
             * [BitonicSort](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/sorts/BitonicSort.java)
             * [BogoSort](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/sorts/BogoSort.java)
@@ -450,6 +452,7 @@
             * [SlowSort](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/sorts/SlowSort.java)
             * [SortAlgorithm](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/sorts/SortAlgorithm.java)
             * [SortUtils](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/sorts/SortUtils.java)
+            * [SortUtilsRandomGenerator](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/sorts/SortUtilsRandomGenerator.java)
             * [StoogeSort](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/sorts/StoogeSort.java)
             * [StrandSort](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/sorts/StrandSort.java)
             * [SwapSort](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/sorts/SwapSort.java)
@@ -496,6 +499,7 @@
             * [CaesarTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/ciphers/CaesarTest.java)
             * [PolybiusTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/ciphers/PolybiusTest.java)
             * [RSATest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/ciphers/RSATest.java)
+            * [SimpleSubCipherTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/ciphers/SimpleSubCipherTest.java)
             * [VigenereTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/ciphers/VigenereTest.java)
           * conversions
             * [BinaryToDecimalTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/conversions/BinaryToDecimalTest.java)
@@ -541,6 +545,7 @@
           * dynamicprogramming
             * [CatalanNumberTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/dynamicprogramming/CatalanNumberTest.java)
             * [EggDroppingTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/dynamicprogramming/EggDroppingTest.java)
+            * [KnapsackMemoizationTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/dynamicprogramming/KnapsackMemoizationTest.java)
             * [SubsetCountTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/dynamicprogramming/SubsetCountTest.java)
           * maths
             * [AbsoluteMaxTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/maths/AbsoluteMaxTest.java)
@@ -586,6 +591,7 @@
             * [PrimeFactorizationTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/maths/PrimeFactorizationTest.java)
             * [PronicNumberTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/maths/PronicNumberTest.java)
             * [PythagoreanTripleTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/maths/PythagoreanTripleTest.java)
+            * [SquareFreeIntegerTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/maths/SquareFreeIntegerTest.java)
             * [SquareRootwithBabylonianMethodTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/maths/SquareRootwithBabylonianMethodTest.java)
             * [SquareRootWithNewtonRaphsonTestMethod](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/maths/SquareRootWithNewtonRaphsonTestMethod.java)
             * [StandardDeviationTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/maths/StandardDeviationTest.java)
@@ -604,6 +610,7 @@
             * [CountCharTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/others/CountCharTest.java)
             * [CountFriendsPairingTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/others/CountFriendsPairingTest.java)
             * [countSetBitsTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/others/countSetBitsTest.java)
+            * [CRC16Test](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/others/CRC16Test.java)
             * [FirstFitCPUTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/others/FirstFitCPUTest.java)
             * [KadaneAlogrithmTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/others/KadaneAlogrithmTest.java)
             * [LinkListSortTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/others/LinkListSortTest.java)
@@ -616,21 +623,30 @@
             * [FCFSSchedulingTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/scheduling/FCFSSchedulingTest.java)
           * searches
             * [BinarySearch2dArrayTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/searches/BinarySearch2dArrayTest.java)
+            * [BreadthFirstSearchTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/searches/BreadthFirstSearchTest.java)
             * [HowManyTimesRotatedTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/searches/HowManyTimesRotatedTest.java)
             * [KMPSearchTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/searches/KMPSearchTest.java)
             * [QuickSelectTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/searches/QuickSelectTest.java)
             * [RabinKarpAlgorithmTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/searches/RabinKarpAlgorithmTest.java)
             * [RowColumnWiseSorted2dArrayBinarySearchTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/searches/RowColumnWiseSorted2dArrayBinarySearchTest.java)
           * sorts
+            * [BeadSortTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/sorts/BeadSortTest.java)
             * [BinaryInsertionSortTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/sorts/BinaryInsertionSortTest.java)
             * [BogoSortTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/sorts/BogoSortTest.java)
             * [BubbleSortTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/sorts/BubbleSortTest.java)
+            * [CocktailShakerSortTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/sorts/CocktailShakerSortTest.java)
             * [DualPivotQuickSortTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/sorts/DualPivotQuickSortTest.java)
             * [DutchNationalFlagSortTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/sorts/DutchNationalFlagSortTest.java)
+            * [HeapSortTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/sorts/HeapSortTest.java)
+            * [InsertionSortTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/sorts/InsertionSortTest.java)
+            * [MergeSortRecursiveTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/sorts/MergeSortRecursiveTest.java)
             * [MergeSortTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/sorts/MergeSortTest.java)
+            * [OddEvenSortTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/sorts/OddEvenSortTest.java)
             * [QuickSortTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/sorts/QuickSortTest.java)
             * [SelectionSortTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/sorts/SelectionSortTest.java)
             * [SlowSortTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/sorts/SlowSortTest.java)
+            * [SortUtilsRandomGeneratorTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/sorts/SortUtilsRandomGeneratorTest.java)
+            * [SortUtilsTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/sorts/SortUtilsTest.java)
             * [StrandSortTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/sorts/StrandSortTest.java)
             * [TopologicalSortTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/sorts/TopologicalSortTest.java)
             * [WiggleSortTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/sorts/WiggleSortTest.java)
diff --git a/src/main/java/com/thealgorithms/dynamicprogramming/KnapsackMemoization.java b/src/main/java/com/thealgorithms/dynamicprogramming/KnapsackMemoization.java
index 8d2b324a..e3cc7cef 100644
--- a/src/main/java/com/thealgorithms/dynamicprogramming/KnapsackMemoization.java
+++ b/src/main/java/com/thealgorithms/dynamicprogramming/KnapsackMemoization.java
@@ -1,51 +1,52 @@
 package com.thealgorithms.dynamicprogramming;
 
-import java.util.Arrays;
-
 /**
  * Recursive Solution for 0-1 knapsack with memoization
+ * This method is basically an extension to the recursive approach so that we
+ * can overcome the problem of calculating redundant cases and thus increased
+ * complexity. We can solve this problem by simply creating a 2-D array that can
+ * store a particular state (n, w) if we get it the first time.
  */
 public class KnapsackMemoization {
 
-    private static int[][] t;
+    int knapSack(int W, int wt[], int val[], int N) {
+
+        // Declare the table dynamically
+        int dp[][] = new int[N + 1][W + 1];
 
-    // 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];
+        // Loop to initially filled the
+        // table with -1
+        for (int i = 0; i < N + 1; i++) {
+            for (int j = 0; j < W + 1; j++) {
+                dp[i][j] = -1;
+            }
         }
+
+        return knapSackRec(W, wt, val, N, dp);
+    }
+
+    // Returns the value of maximum profit using Recursive approach
+    int knapSackRec(int W, int wt[],
+            int val[], int n,
+            int[][] dp) {
+
+        // Base condition
         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];
+
+        if (dp[n][W] != -1) {
+            return dp[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);
+        if (wt[n - 1] > W) {
+            // Store the value of function call stack in table
+            dp[n][W] = knapSackRec(W, wt, val, n - 1, dp);
+            return dp[n][W];
+        } else {
+            // Return value of table after storing
+            return dp[n][W] = Math.max((val[n - 1] + knapSackRec(W - wt[n - 1], wt, val, n - 1, dp)),
+                    knapSackRec(W, wt, val, n - 1, dp));
+        }
     }
 }
diff --git a/src/main/java/com/thealgorithms/dynamicprogramming/MemoizationTechniqueKnapsack.java b/src/main/java/com/thealgorithms/dynamicprogramming/MemoizationTechniqueKnapsack.java
deleted file mode 100644
index bd64c364..00000000
--- a/src/main/java/com/thealgorithms/dynamicprogramming/MemoizationTechniqueKnapsack.java
+++ /dev/null
@@ -1,68 +0,0 @@
-package com.thealgorithms.dynamicprogramming;
-
-// Here is the top-down approach of
-// dynamic programming
-
-public class MemoizationTechniqueKnapsack {
-
-    // A utility function that returns
-    // maximum of two integers
-    static int max(int a, int b) {
-        return (a > b) ? a : b;
-    }
-
-    // Returns the value of maximum profit
-    static int knapSackRec(int W, int wt[], int val[], int n, int[][] dp) {
-        // Base condition
-        if (n == 0 || W == 0) {
-            return 0;
-        }
-
-        if (dp[n][W] != -1) {
-            return dp[n][W];
-        }
-
-        if (
-            wt[n - 1] > W
-        ) { // stack in table before return // Store the value of function call
-            return dp[n][W] = knapSackRec(W, wt, val, n - 1, dp);
-        } else { // Return value of table after storing
-            return (
-                dp[n][W] =
-                    max(
-                        (
-                            val[n - 1] +
-                            knapSackRec(W - wt[n - 1], wt, val, n - 1, dp)
-                        ),
-                        knapSackRec(W, wt, val, n - 1, dp)
-                    )
-            );
-        }
-    }
-
-    static int knapSack(int W, int wt[], int val[], int N) {
-        // Declare the table dynamically
-        int dp[][] = new int[N + 1][W + 1];
-
-        // Loop to initially filled the
-        // table with -1
-        for (int i = 0; i < N + 1; i++) {
-            for (int j = 0; j < W + 1; j++) {
-                dp[i][j] = -1;
-            }
-        }
-
-        return knapSackRec(W, wt, val, N, dp);
-    }
-
-    // Driver Code
-    public static void main(String[] args) {
-        int val[] = { 60, 100, 120 };
-        int wt[] = { 10, 20, 30 };
-
-        int W = 50;
-        int N = val.length;
-
-        System.out.println(knapSack(W, wt, val, N));
-    }
-}


Test patch:
diff --git a/src/test/java/com/thealgorithms/dynamicprogramming/KnapsackMemoizationTest.java b/src/test/java/com/thealgorithms/dynamicprogramming/KnapsackMemoizationTest.java
new file mode 100644
index 00000000..7d06618c
--- /dev/null
+++ b/src/test/java/com/thealgorithms/dynamicprogramming/KnapsackMemoizationTest.java
@@ -0,0 +1,34 @@
+package com.thealgorithms.dynamicprogramming;
+
+import org.junit.jupiter.api.Test;
+import static org.junit.jupiter.api.Assertions.*;
+
+public class KnapsackMemoizationTest {
+
+    KnapsackMemoization knapsackMemoization = new KnapsackMemoization();
+
+    @Test
+    void Test1() {
+        int[] weight = { 1, 3, 4, 5 };
+        int[] value = { 1, 4, 5, 7 };
+        int capacity = 10;
+        assertEquals(13, knapsackMemoization.knapSack(capacity, weight, value, weight.length));
+    }
+
+    @Test
+    void Test2() {
+        int[] weight = { 95, 4, 60, 32, 23, 72, 80, 62, 65, 46 };
+        int[] value = { 55, 10, 47, 5, 4, 50, 8, 61, 85, 87 };
+        int capacity = 269;
+        assertEquals(295, knapsackMemoization.knapSack(capacity, weight, value, weight.length));
+    }
+
+    @Test
+    void Test3() {
+        int[] weight = { 10, 20, 30 };
+        int[] value = { 60, 100, 120 };
+        int capacity = 50;
+        assertEquals(220, knapsackMemoization.knapSack(capacity, weight, value, weight.length));
+    }
+
+}
\ No newline at end of file