Repository: TheAlgorithms/Java
Pull request #6425 (2025-07-21 14:18:03)

Feat(Improved): Add 0/1 Knapsack Problem: Recursive and Tabulation (Bottom-Up DP) Implementations in Java along with their corresponding Tests 
1.Recursive Solution
-Uses a top-down approach without memoization.
-Highlights the decision process for including or excluding each item.
2.Tabulation (Bottom-Up DP) Solution
-Efficient dynamic programming approach using a 2D table.
-Includes a utility function to print the DP table.
-Demonstrates space-time tradeoff compared to recursion.

Both implementations follow consistent formatting, inline documentation, and are aligned with the repository's existing code structure.

codecov-commenter: ## [Codecov](https://app.codecov.io/gh/TheAlgorithms/Java/pull/6425?dropdown=coverage&src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) Report
Attention: Patch coverage is `72.72727%` with `9 lines` in your changes missing coverage. Please review.
> Project coverage is 74.86%. Comparing base [(`31bf130`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/31bf130e9eb14409c6f628f0a64a419fc6564e61?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) to head [(`40b8bc5`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/40b8bc5e2c5aa5691c746e9c64d1ab69e2cbb121?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).

| [Files with missing lines](https://app.codecov.io/gh/TheAlgorithms/Java/pull/6425?dropdown=coverage&src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) | Patch % | Lines |
|---|---|---|
| [.../dynamicprogramming/KnapsackZeroOneTabulation.java](https://app.codecov.io/gh/TheAlgorithms/Java/pull/6425?src=pr&el=tree&filepath=src%2Fmain%2Fjava%2Fcom%2Fthealgorithms%2Fdynamicprogramming%2FKnapsackZeroOneTabulation.java&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms#diff-c3JjL21haW4vamF2YS9jb20vdGhlYWxnb3JpdGhtcy9keW5hbWljcHJvZ3JhbW1pbmcvS25hcHNhY2taZXJvT25lVGFidWxhdGlvbi5qYXZh) | 60.00% | [4 Missing and 4 partials :warning: ](https://app.codecov.io/gh/TheAlgorithms/Java/pull/6425?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) |
| [...algorithms/dynamicprogramming/KnapsackZeroOne.java](https://app.codecov.io/gh/TheAlgorithms/Java/pull/6425?src=pr&el=tree&filepath=src%2Fmain%2Fjava%2Fcom%2Fthealgorithms%2Fdynamicprogramming%2FKnapsackZeroOne.java&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms#diff-c3JjL21haW4vamF2YS9jb20vdGhlYWxnb3JpdGhtcy9keW5hbWljcHJvZ3JhbW1pbmcvS25hcHNhY2taZXJvT25lLmphdmE=) | 92.30% | [0 Missing and 1 partial :warning: ](https://app.codecov.io/gh/TheAlgorithms/Java/pull/6425?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) |

<details><summary>Additional details and impacted files</summary>


```diff
@@            Coverage Diff            @@
##             master    #6425   +/-   ##
=========================================
  Coverage     74.86%   74.86%           
- Complexity     5482     5496   +14     
=========================================
  Files           682      684    +2     
  Lines         19012    19045   +33     
  Branches       3670     3680   +10     
=========================================
+ Hits          14233    14258   +25     
- Misses         4224     4228    +4     
- Partials        555      559    +4     
```

</details>

[:umbrella: View full report in Codecov by Sentry](https://app.codecov.io/gh/TheAlgorithms/Java/pull/6425?dropdown=coverage&src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).   
:loudspeaker: Have feedback on the report? [Share it here](https://about.codecov.io/codecov-pr-comment-feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).

<details><summary> :rocket: New features to boost your workflow: </summary>

- :snowflake: [Test Analytics](https://docs.codecov.com/docs/test-analytics): Detect flaky tests, report on failures, and find test suite problems.
</details>

Patch:
diff --git a/src/main/java/com/thealgorithms/dynamicprogramming/KnapsackZeroOne.java b/src/main/java/com/thealgorithms/dynamicprogramming/KnapsackZeroOne.java
new file mode 100644
index 00000000..abc1e321
--- /dev/null
+++ b/src/main/java/com/thealgorithms/dynamicprogramming/KnapsackZeroOne.java
@@ -0,0 +1,53 @@
+package com.thealgorithms.dynamicprogramming;
+
+/**
+ * The {@code KnapsackZeroOne} provides Recursive solution for the 0/1 Knapsack
+ * problem. Solves by exploring all combinations of items using recursion. No
+ * memoization or dynamic programming optimizations are applied.
+ *
+ * Time Complexity: O(2^n) — explores all subsets.
+ * Space Complexity: O(n) — due to recursive call stack.
+ *
+ * Problem Reference: https://en.wikipedia.org/wiki/Knapsack_problem
+ */
+public final class KnapsackZeroOne {
+
+    private KnapsackZeroOne() {
+        // Prevent instantiation
+    }
+
+    /**
+     * Solves the 0/1 Knapsack problem using recursion.
+     *
+     * @param values   the array containing values of the items
+     * @param weights  the array containing weights of the items
+     * @param capacity the total capacity of the knapsack
+     * @param n        the number of items
+     * @return the maximum total value achievable within the given weight limit
+     * @throws IllegalArgumentException if input arrays are null, empty, or
+     *     lengths mismatch
+     */
+    public static int compute(final int[] values, final int[] weights, final int capacity, final int n) {
+        if (values == null || weights == null) {
+            throw new IllegalArgumentException("Input arrays cannot be null.");
+        }
+        if (values.length != weights.length) {
+            throw new IllegalArgumentException("Value and weight arrays must be of the same length.");
+        }
+        if (capacity < 0 || n < 0) {
+            throw new IllegalArgumentException("Invalid input: arrays must be non-empty and capacity/n "
+                + "non-negative.");
+        }
+        if (n == 0 || capacity == 0 || values.length == 0) {
+            return 0;
+        }
+
+        if (weights[n - 1] <= capacity) {
+            final int include = values[n - 1] + compute(values, weights, capacity - weights[n - 1], n - 1);
+            final int exclude = compute(values, weights, capacity, n - 1);
+            return Math.max(include, exclude);
+        } else {
+            return compute(values, weights, capacity, n - 1);
+        }
+    }
+}
diff --git a/src/main/java/com/thealgorithms/dynamicprogramming/KnapsackZeroOneTabulation.java b/src/main/java/com/thealgorithms/dynamicprogramming/KnapsackZeroOneTabulation.java
new file mode 100644
index 00000000..c560efc6
--- /dev/null
+++ b/src/main/java/com/thealgorithms/dynamicprogramming/KnapsackZeroOneTabulation.java
@@ -0,0 +1,69 @@
+package com.thealgorithms.dynamicprogramming;
+
+/**
+ * Tabulation (Bottom-Up) Solution for 0-1 Knapsack Problem.
+ * This method uses dynamic programming to build up a solution iteratively,
+ * filling a 2-D array where each entry dp[i][w] represents the maximum value
+ * achievable with the first i items and a knapsack capacity of w.
+ *
+ * The tabulation approach is efficient because it avoids redundant calculations
+ * by solving all subproblems in advance and storing their results, ensuring
+ * each subproblem is solved only once. This is a key technique in dynamic programming,
+ * making it possible to solve problems that would otherwise be infeasible due to
+ * exponential time complexity in naive recursive solutions.
+ *
+ * Time Complexity: O(n * W), where n is the number of items and W is the knapsack capacity.
+ * Space Complexity: O(n * W) for the DP table.
+ *
+ * For more information, see:
+ * https://en.wikipedia.org/wiki/Knapsack_problem#Dynamic_programming
+ */
+public final class KnapsackZeroOneTabulation {
+
+    private KnapsackZeroOneTabulation() {
+        // Prevent instantiation
+    }
+
+    /**
+     * Solves the 0-1 Knapsack problem using the bottom-up tabulation technique.
+     * @param values the values of the items
+     * @param weights the weights of the items
+     * @param capacity the total capacity of the knapsack
+     * @param itemCount the number of items
+     * @return the maximum value that can be put in the knapsack
+     * @throws IllegalArgumentException if input arrays are null, of different lengths,or if capacity or itemCount is invalid
+     */
+    public static int compute(final int[] values, final int[] weights, final int capacity, final int itemCount) {
+        if (values == null || weights == null) {
+            throw new IllegalArgumentException("Values and weights arrays must not be null.");
+        }
+        if (values.length != weights.length) {
+            throw new IllegalArgumentException("Values and weights arrays must be non-null and of same length.");
+        }
+        if (capacity < 0) {
+            throw new IllegalArgumentException("Capacity must not be negative.");
+        }
+        if (itemCount < 0 || itemCount > values.length) {
+            throw new IllegalArgumentException("Item count must be between 0 and the length of the values array.");
+        }
+
+        final int[][] dp = new int[itemCount + 1][capacity + 1];
+
+        for (int i = 1; i <= itemCount; i++) {
+            final int currentValue = values[i - 1];
+            final int currentWeight = weights[i - 1];
+
+            for (int w = 1; w <= capacity; w++) {
+                if (currentWeight <= w) {
+                    final int includeItem = currentValue + dp[i - 1][w - currentWeight];
+                    final int excludeItem = dp[i - 1][w];
+                    dp[i][w] = Math.max(includeItem, excludeItem);
+                } else {
+                    dp[i][w] = dp[i - 1][w];
+                }
+            }
+        }
+
+        return dp[itemCount][capacity];
+    }
+}


Test patch:
diff --git a/src/test/java/com/thealgorithms/dynamicprogramming/KnapsackZeroOneTabulationTest.java b/src/test/java/com/thealgorithms/dynamicprogramming/KnapsackZeroOneTabulationTest.java
new file mode 100644
index 00000000..6c61ad21
--- /dev/null
+++ b/src/test/java/com/thealgorithms/dynamicprogramming/KnapsackZeroOneTabulationTest.java
@@ -0,0 +1,78 @@
+package com.thealgorithms.dynamicprogramming;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+import static org.junit.jupiter.api.Assertions.assertThrows;
+
+import org.junit.jupiter.api.Test;
+
+public class KnapsackZeroOneTabulationTest {
+
+    @Test
+    public void basicCheck() {
+        int[] values = {60, 100, 120};
+        int[] weights = {10, 20, 30};
+        int capacity = 50;
+        int itemCount = values.length;
+
+        int expected = 220; // Best choice: item 1 (100) and item 2 (120)
+        int result = KnapsackZeroOneTabulation.compute(values, weights, capacity, itemCount);
+        assertEquals(expected, result);
+    }
+
+    @Test
+    public void emptyKnapsack() {
+        int[] values = {};
+        int[] weights = {};
+        int capacity = 50;
+        int itemCount = 0;
+
+        assertEquals(0, KnapsackZeroOneTabulation.compute(values, weights, capacity, itemCount));
+    }
+
+    @Test
+    public void zeroCapacity() {
+        int[] values = {60, 100, 120};
+        int[] weights = {10, 20, 30};
+        int capacity = 0;
+        int itemCount = values.length;
+
+        assertEquals(0, KnapsackZeroOneTabulation.compute(values, weights, capacity, itemCount));
+    }
+
+    @Test
+    public void negativeCapacity() {
+        int[] values = {10, 20, 30};
+        int[] weights = {1, 1, 1};
+        int capacity = -10;
+        int itemCount = values.length;
+
+        IllegalArgumentException exception = assertThrows(IllegalArgumentException.class, () -> KnapsackZeroOneTabulation.compute(values, weights, capacity, itemCount));
+        assertEquals("Capacity must not be negative.", exception.getMessage());
+    }
+
+    @Test
+    public void mismatchedLengths() {
+        int[] values = {60, 100}; // Only 2 values
+        int[] weights = {10, 20, 30}; // 3 weights
+        int capacity = 50;
+        int itemCount = 2; // Matches `values.length`
+
+        // You could either expect 0 or throw an IllegalArgumentException in your compute function
+        assertThrows(IllegalArgumentException.class, () -> { KnapsackZeroOneTabulation.compute(values, weights, capacity, itemCount); });
+    }
+
+    @Test
+    public void nullInputs() {
+        int[] weights = {1, 2, 3};
+        int capacity = 10;
+        int itemCount = 3;
+
+        IllegalArgumentException exception1 = assertThrows(IllegalArgumentException.class, () -> KnapsackZeroOneTabulation.compute(null, weights, capacity, itemCount));
+        assertEquals("Values and weights arrays must not be null.", exception1.getMessage());
+
+        int[] values = {1, 2, 3};
+
+        IllegalArgumentException exception2 = assertThrows(IllegalArgumentException.class, () -> KnapsackZeroOneTabulation.compute(values, null, capacity, itemCount));
+        assertEquals("Values and weights arrays must not be null.", exception2.getMessage());
+    }
+}
diff --git a/src/test/java/com/thealgorithms/dynamicprogramming/KnapsackZeroOneTest.java b/src/test/java/com/thealgorithms/dynamicprogramming/KnapsackZeroOneTest.java
new file mode 100644
index 00000000..0ca2b91f
--- /dev/null
+++ b/src/test/java/com/thealgorithms/dynamicprogramming/KnapsackZeroOneTest.java
@@ -0,0 +1,68 @@
+package com.thealgorithms.dynamicprogramming;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+import static org.junit.jupiter.api.Assertions.assertThrows;
+
+import org.junit.jupiter.api.Test;
+
+class KnapsackZeroOneTest {
+
+    @Test
+    void basicCheck() {
+        int[] values = {60, 100, 120};
+        int[] weights = {10, 20, 30};
+        int capacity = 50;
+        int expected = 220;
+
+        int result = KnapsackZeroOne.compute(values, weights, capacity, values.length);
+        assertEquals(expected, result);
+    }
+
+    @Test
+    void zeroCapacity() {
+        int[] values = {10, 20, 30};
+        int[] weights = {1, 1, 1};
+        int capacity = 0;
+
+        int result = KnapsackZeroOne.compute(values, weights, capacity, values.length);
+        assertEquals(0, result);
+    }
+
+    @Test
+    void zeroItems() {
+        int[] values = {};
+        int[] weights = {};
+        int capacity = 10;
+
+        int result = KnapsackZeroOne.compute(values, weights, capacity, 0);
+        assertEquals(0, result);
+    }
+
+    @Test
+    void weightsExceedingCapacity() {
+        int[] values = {10, 20};
+        int[] weights = {100, 200};
+        int capacity = 50;
+
+        int result = KnapsackZeroOne.compute(values, weights, capacity, values.length);
+        assertEquals(0, result);
+    }
+
+    @Test
+    void throwsOnNullArrays() {
+        assertThrows(IllegalArgumentException.class, () -> KnapsackZeroOne.compute(null, new int[] {1}, 10, 1));
+        assertThrows(IllegalArgumentException.class, () -> KnapsackZeroOne.compute(new int[] {1}, null, 10, 1));
+    }
+
+    @Test
+    void throwsOnMismatchedArrayLengths() {
+        assertThrows(IllegalArgumentException.class, () -> KnapsackZeroOne.compute(new int[] {10, 20}, new int[] {5}, 15, 2));
+    }
+
+    @Test
+    void throwsOnNegativeInputs() {
+        assertThrows(IllegalArgumentException.class, () -> KnapsackZeroOne.compute(new int[] {10}, new int[] {5}, -1, 1));
+
+        assertThrows(IllegalArgumentException.class, () -> KnapsackZeroOne.compute(new int[] {10}, new int[] {5}, 5, -1));
+    }
+}