feat: Add 0/1 Knapsack and its tabulation implementation with their c…

…orresponding tests
TheAlgorithms · alxkm · Jul 22, 2025 · Jul 20, 2025 · Jul 20, 2025 · Jul 20, 2025
commit 36fd4b2e3a8b71dd24bf0c7656958180d46f2e58
diff --git a/src/main/java/com/thealgorithms/dynamicprogramming/ZeroOneKnapsack.java b/src/main/java/com/thealgorithms/dynamicprogramming/ZeroOneKnapsack.java
@@ -22,17 +22,17 @@ private ZeroOneKnapsack() {
      * @param n the number of items
      * @return the maximum total value achievable within the given weight limit
      */
-    public static int KnapsackCompute(int[] values, int[] weights, int capacity, int n) {
+    public static int compute(int[] values, int[] weights, int capacity, int n) {
         if (n == 0 || capacity == 0) {
             return 0;
         }
 
         if (weights[n - 1] <= capacity) {
-            int include = values[n - 1] + KnapsackCompute(values, weights, capacity - weights[n - 1], n - 1);
-            int exclude = KnapsackCompute(values, weights, capacity, n - 1);
+            int include = values[n - 1] + compute(values, weights, capacity - weights[n - 1], n - 1);
+            int exclude = compute(values, weights, capacity, n - 1);
             return Math.max(include, exclude);
         } else {
-            return KnapsackCompute(values, weights, capacity, n - 1);
+            return compute(values, weights, capacity, n - 1);
         }
     }
 }
diff --git a/src/main/java/com/thealgorithms/dynamicprogramming/ZeroOneKnapsackTab.java b/src/main/java/com/thealgorithms/dynamicprogramming/ZeroOneKnapsackTab.java
@@ -4,11 +4,11 @@
  * The {@code ZeroOneKnapsackTab} class provides a method to solve the 0-1 Knapsack problem
  * using dynamic programming (tabulation approach).
  *
- * <p>0-1 Knapsack Problem - 
+ * <p>0-1 Knapsack Problem -
  * Given weights and values of n items, and a maximum weight W,
  * determine the maximum total value of items that can be included in the knapsack
  * such that their total weight does not exceed W. Each item can be picked only once.
- * 
+ *
  * Problem Link: https://www.geeksforgeeks.org/0-1-knapsack-problem-dp-10/
  */
 public final class ZeroOneKnapsackTab {
@@ -26,7 +26,7 @@ private ZeroOneKnapsackTab() {
      * @param n the number of items
      * @return the maximum value that can be put in the knapsack
      */
-    public static int kcompute(int[] val, int[] wt, int W, int n) {
+    public static int compute(int[] val, int[] wt, int W, int n) {
         int[][] dp = new int[n + 1][W + 1];
 
         for (int i = 1; i <= n; i++) {

diff --git a/src/test/java/com/thealgorithms/dynamicprogramming/ZeroOneKnapsackTabTest.java b/src/test/java/com/thealgorithms/dynamicprogramming/ZeroOneKnapsackTabTest.java
@@ -20,7 +20,7 @@ public void testKnownValues() {
         int n = val.length;
 
         // Expected result is 220 (items with weight 20 and 30)
-        assertEquals(220, ZeroOneKnapsackTab.kcompute(val, wt, W, n), "Maximum value for capacity 50 should be 220.");
+        assertEquals(220, ZeroOneKnapsackTab.compute(val, wt, W, n), "Maximum value for capacity 50 should be 220.");
     }
 
     @Test
@@ -31,7 +31,7 @@ public void testZeroCapacity() {
         int n = val.length;
 
         // With zero capacity, the result should be 0
-        assertEquals(0, ZeroOneKnapsackTab.kcompute(val, wt, W, n), "Maximum value for capacity 0 should be 0.");
+        assertEquals(0, ZeroOneKnapsackTab.compute(val, wt, W, n), "Maximum value for capacity 0 should be 0.");
     }
 
     @Test
@@ -42,7 +42,7 @@ public void testZeroItems() {
         int n = val.length;
 
         // With no items, the result should be 0
-        assertEquals(0, ZeroOneKnapsackTab.kcompute(val, wt, W, n), "Maximum value with no items should be 0.");
+        assertEquals(0, ZeroOneKnapsackTab.compute(val, wt, W, n), "Maximum value with no items should be 0.");
     }
 
     @Test
@@ -53,6 +53,6 @@ public void testExactFit() {
         int n = val.length;
 
         // All items fit exactly into capacity 6
-        assertEquals(30, ZeroOneKnapsackTab.kcompute(val, wt, W, n), "Maximum value for exact fit should be 30.");
+        assertEquals(30, ZeroOneKnapsackTab.compute(val, wt, W, n), "Maximum value for exact fit should be 30.");
     }
 }
diff --git a/src/test/java/com/thealgorithms/dynamicprogramming/ZeroOneKnapsackTest.java b/src/test/java/com/thealgorithms/dynamicprogramming/ZeroOneKnapsackTest.java
@@ -17,8 +17,7 @@ public void testKnapsackBasic() {
         int[] val = {15, 14, 10, 45, 30};
         int[] wt = {2, 5, 1, 3, 4};
         int W = 7;
-        assertEquals(75, ZeroOneKnapsack.KnapsackCompute(val, wt, W, val.length), 
-            "Expected maximum value is 75.");
+        assertEquals(75, ZeroOneKnapsack.compute(val, wt, W, val.length), "Expected maximum value is 75.");
     }
 
     /**
@@ -29,8 +28,7 @@ public void testZeroCapacity() {
         int[] val = {10, 20, 30};
         int[] wt = {1, 1, 1};
         int W = 0;
-        assertEquals(0, ZeroOneKnapsack.KnapsackCompute(val, wt, W, val.length), 
-            "Expected maximum value is 0 for zero capacity.");
+        assertEquals(0, ZeroOneKnapsack.compute(val, wt, W, val.length), "Expected maximum value is 0 for zero capacity.");
     }
 
     /**
@@ -41,8 +39,7 @@ public void testNoItems() {
         int[] val = {};
         int[] wt = {};
         int W = 10;
-        assertEquals(0, ZeroOneKnapsack.KnapsackCompute(val, wt, W, 0), 
-            "Expected maximum value is 0 when no items are available.");
+        assertEquals(0, ZeroOneKnapsack.compute(val, wt, W, 0), "Expected maximum value is 0 when no items are available.");
     }
 
     /**
@@ -53,7 +50,6 @@ public void testExactFit() {
         int[] val = {60, 100, 120};
         int[] wt = {10, 20, 30};
         int W = 50;
-        assertEquals(220, ZeroOneKnapsack.KnapsackCompute(val, wt, W, val.length), 
-            "Expected maximum value is 220 for exact fit.");
+        assertEquals(220, ZeroOneKnapsack.compute(val, wt, W, val.length), "Expected maximum value is 220 for exact fit.");
     }
 }