Repository: TheAlgorithms/Java
Pull request #4368 (2023-09-11 08:49:32)

#4367 Enhance Knapsack problem
<!-- For completed items, change [ ] to [x] -->

- [x] I have read [CONTRIBUTING.md](https://github.com/TheAlgorithms/Java/blob/master/CONTRIBUTING.md).
- [x] This pull request is all my own work -- I have not plagiarized it.
- [x] All filenames are in PascalCase.
- [x] All functions and variable names follow Java naming conventions.
- [x] All new algorithms have a URL in their comments that points to Wikipedia or other similar explanations.

Reduced space complexity of solution from O(n*w) to O(w)
Named variables better
Added testfile

All code is covered in testcases
<img width="780" alt="Screenshot 2023-09-11 at 2 03 35 PM" src="https://github.com/TheAlgorithms/Java/assets/76104205/77077e0d-07c8-407e-8fe9-0b93b1192bd9">


Manan-09: Seems like this is  [DyanamicProgrammingKnapsack](https://github.com/TheAlgorithms/Java/blob/94621fb63eafcf18666dfad176fffc28f82b439a/src/main/java/com/thealgorithms/dynamicprogramming/DyanamicProgrammingKnapsack.java#L5) duplicate of what I just refactored, and  [KnapsackMemoization.java](https://github.com/TheAlgorithms/Java/blob/94621fb63eafcf18666dfad176fffc28f82b439a/src/main/java/com/thealgorithms/dynamicprogramming/KnapsackMemoization.java#L12) is recursive solition of this problem.
But my solution has better space complexity with same TC
vil02: > Seems like this is [DyanamicProgrammingKnapsack](https://github.com/TheAlgorithms/Java/blob/94621fb63eafcf18666dfad176fffc28f82b439a/src/main/java/com/thealgorithms/dynamicprogramming/DyanamicProgrammingKnapsack.java#L5) duplicate of what I just refactored, and [KnapsackMemoization.java](https://github.com/TheAlgorithms/Java/blob/94621fb63eafcf18666dfad176fffc28f82b439a/src/main/java/com/thealgorithms/dynamicprogramming/KnapsackMemoization.java#L12) is recursive solition of this problem. But my solution has better space complexity with same TC

@siriak how should we proceed?
siriak: Please remove the duplicate, but leave the version with memoization as it's a different approach
Manan-09: 
> What if one of the entries of `weights` is negative or `0`?
> 
> The following code:
> 
> ```java
> Knapsack.knapSack(1, new int[]{0, 0, 0, 0}, new int[]{1, 1, 1, 1})
> ```
> 
> gives me `16` and I think the correct answer should be `4`.

Knapsack problem have positive weights normally, should we add extra check for non positive weights ?

vil02: > Knapsack problem have positive weights normally, should we add extra check for non positive weights ?
Yes! Throwing an error is the best way of saying that non-positive weights are forbidden.


Patch:
diff --git a/src/main/java/com/thealgorithms/dynamicprogramming/DyanamicProgrammingKnapsack.java b/src/main/java/com/thealgorithms/dynamicprogramming/DyanamicProgrammingKnapsack.java
deleted file mode 100644
index 042dff37..00000000
--- a/src/main/java/com/thealgorithms/dynamicprogramming/DyanamicProgrammingKnapsack.java
+++ /dev/null
@@ -1,36 +0,0 @@
-package com.thealgorithms.dynamicprogramming;
-
-// A Dynamic Programming based solution
-// for 0-1 Knapsack problem
-public class DyanamicProgrammingKnapsack {
-    // Returns the maximum value that can
-    // be put in a knapsack of capacity W
-    static int knapSack(int W, int[] wt, int[] val, int n) {
-        int i, w;
-        int[][] K = new int[n + 1][W + 1];
-
-        // Build table K[][] in bottom up manner
-        for (i = 0; i <= n; i++) {
-            for (w = 0; w <= W; w++) {
-                if (i == 0 || w == 0) {
-                    K[i][w] = 0;
-                } else if (wt[i - 1] <= w) {
-                    K[i][w] = Math.max(val[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w]);
-                } else {
-                    K[i][w] = K[i - 1][w];
-                }
-            }
-        }
-
-        return K[n][W];
-    }
-
-    // Driver code
-    public static void main(String[] args) {
-        int[] val = new int[] {60, 100, 120};
-        int[] wt = new int[] {10, 20, 30};
-        int W = 50;
-        int n = val.length;
-        System.out.println(knapSack(W, wt, val, n));
-    }
-}
diff --git a/src/main/java/com/thealgorithms/dynamicprogramming/Knapsack.java b/src/main/java/com/thealgorithms/dynamicprogramming/Knapsack.java
index 712a028e..13456176 100644
--- a/src/main/java/com/thealgorithms/dynamicprogramming/Knapsack.java
+++ b/src/main/java/com/thealgorithms/dynamicprogramming/Knapsack.java
@@ -1,38 +1,55 @@
 package com.thealgorithms.dynamicprogramming;
 
+import java.util.Arrays;
+
 /**
- * A DynamicProgramming based solution for 0-1 Knapsack problem
+ * A Dynamic Programming based solution for the 0-1 Knapsack problem.
+ * This class provides a method, `knapSack`, that calculates the maximum value that can be
+ * obtained from a given set of items with weights and values, while not exceeding a
+ * given weight capacity.
+ *
+ * @see <a href="https://en.wikipedia.org/?title=0-1_Knapsack_problem">0-1 Knapsack Problem </a>
  */
-public class Knapsack {
+public final class Knapsack {
+
+    private Knapsack() {
+    }
 
-    private static int knapSack(int W, int[] wt, int[] val, int n) throws IllegalArgumentException {
-        if (wt == null || val == null) {
-            throw new IllegalArgumentException();
+    private static void throwIfInvalidInput(final int weightCapacity, final int[] weights, final int[] values) {
+        if (weightCapacity < 0) {
+            throw new IllegalArgumentException("Weight capacity should not be negative.");
         }
-        int i, w;
-        int[][] rv = new int[n + 1][W + 1]; // rv means return value
-
-        // Build table rv[][] in bottom up manner
-        for (i = 0; i <= n; i++) {
-            for (w = 0; w <= W; w++) {
-                if (i == 0 || w == 0) {
-                    rv[i][w] = 0;
-                } else if (wt[i - 1] <= w) {
-                    rv[i][w] = Math.max(val[i - 1] + rv[i - 1][w - wt[i - 1]], rv[i - 1][w]);
-                } else {
-                    rv[i][w] = rv[i - 1][w];
+        if (weights == null || values == null || weights.length != values.length) {
+            throw new IllegalArgumentException("Input arrays must not be null and must have the same length.");
+        }
+        if (Arrays.stream(weights).anyMatch(w -> w <= 0)) {
+            throw new IllegalArgumentException("Input array should not contain non-positive weight(s).");
+        }
+    }
+
+    /**
+     * Solves the 0-1 Knapsack problem using Dynamic Programming.
+     *
+     * @param weightCapacity The maximum weight capacity of the knapsack.
+     * @param weights        An array of item weights.
+     * @param values         An array of item values.
+     * @return The maximum value that can be obtained without exceeding the weight capacity.
+     * @throws IllegalArgumentException If the input arrays are null or have different lengths.
+     */
+    public static int knapSack(final int weightCapacity, final int[] weights, final int[] values) throws IllegalArgumentException {
+        throwIfInvalidInput(weightCapacity, weights, values);
+
+        // DP table to store the state of the maximum possible return for a given weight capacity.
+        int[] dp = new int[weightCapacity + 1];
+
+        for (int i = 0; i < values.length; i++) {
+            for (int w = weightCapacity; w > 0; w--) {
+                if (weights[i] <= w) {
+                    dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
                 }
             }
         }
 
-        return rv[n][W];
-    }
-
-    // Driver program to test above function
-    public static void main(String[] args) {
-        int[] val = new int[] {50, 100, 130};
-        int[] wt = new int[] {10, 20, 40};
-        int W = 50;
-        System.out.println(knapSack(W, wt, val, val.length));
+        return dp[weightCapacity];
     }
 }


Test patch:
diff --git a/src/test/java/com/thealgorithms/dynamicprogramming/KnapsackTest.java b/src/test/java/com/thealgorithms/dynamicprogramming/KnapsackTest.java
new file mode 100644
index 00000000..3ff733db
--- /dev/null
+++ b/src/test/java/com/thealgorithms/dynamicprogramming/KnapsackTest.java
@@ -0,0 +1,81 @@
+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 KnapsackTest {
+    @Test
+    public void testKnapSackBasic() {
+        int[] weights = {2, 3, 4, 5};
+        int[] values = {3, 4, 5, 6};
+        int weightCapacity = 5;
+        int expected = 7; // Maximum value should be 7 (items 1 and 4).
+        int result = Knapsack.knapSack(weightCapacity, weights, values);
+        assertEquals(expected, result);
+    }
+
+    @Test
+    public void testKnapSackEmpty() {
+        int[] weights = {};
+        int[] values = {};
+        int weightCapacity = 10;
+        int expected = 0; // With no items, the result should be 0.
+        int result = Knapsack.knapSack(weightCapacity, weights, values);
+        assertEquals(expected, result);
+    }
+
+    @Test
+    public void testKnapSackNoCapacity() {
+        int[] weights = {2, 3, 4};
+        int[] values = {3, 4, 5};
+        int weightCapacity = 0;
+        int expected = 0; // With no capacity, the result should be 0.
+        int result = Knapsack.knapSack(weightCapacity, weights, values);
+        assertEquals(expected, result);
+    }
+
+    @Test
+    public void testKnapSackMaxCapacity() {
+        int[] weights = {2, 3, 4, 5};
+        int[] values = {3, 4, 5, 6};
+        int weightCapacity = 10;
+        int expected = 13; // Maximum value should be 13 (items 1, 3, and 4).
+        int result = Knapsack.knapSack(weightCapacity, weights, values);
+        assertEquals(expected, result);
+    }
+
+    @Test
+    public void testKnapSackThrowsForInputsOfDifferentLength() {
+        int[] weights = {2, 3, 4};
+        int[] values = {3, 4, 5, 6}; // Different length values array.
+        int weightCapacity = 5;
+        assertThrows(IllegalArgumentException.class, () -> { Knapsack.knapSack(weightCapacity, weights, values); });
+    }
+
+    @Test
+    public void testKnapSackThrowsForNullInputs() {
+        int[] weights = {2, 3, 4};
+        int[] values = {3, 4, 6};
+        int weightCapacity = 5;
+        assertThrows(IllegalArgumentException.class, () -> { Knapsack.knapSack(weightCapacity, null, values); });
+        assertThrows(IllegalArgumentException.class, () -> { Knapsack.knapSack(weightCapacity, weights, null); });
+    }
+
+    @Test
+    public void testKnapSackThrowsForNegativeCapacity() {
+        int[] weights = {2, 3, 4, 5};
+        int[] values = {3, 4, 5, 6};
+        int weightCapacity = -5;
+        assertThrows(IllegalArgumentException.class, () -> { Knapsack.knapSack(weightCapacity, weights, values); });
+    }
+
+    @Test
+    public void testKnapSackThrowsForNegativeWeight() {
+        int[] weights = {2, 0, 4};
+        int[] values = {3, 4, 6};
+        int weightCapacity = 5;
+        assertThrows(IllegalArgumentException.class, () -> { Knapsack.knapSack(weightCapacity, weights, values); });
+    }
+}