Skip to content

Commit 12b6c29

Browse files
Manan-09vil02
Manan-09
and
vil02
authored
TheAlgorithms#4367 Enhance Knapsack problem (TheAlgorithms#4368)
* Enhance Knapsack problem * Linter solved * Linter solved * Remove DynamicProgrammingKnapsack file, duplicate of Knapsack file * Add null input testcase * Linter resolved * Updated meaningful test names * Add check for negative weightCapacity * Linter resolved * Linter resolved * Add check for non-positive weight * Linter resolved * fix: use proper formatting * fix: use proper formatting * fix: use proper formatting (I hope this will work now) Sorry for the previous mess. * Code review comments * Code review comments * Code review comments * Code review comments --------- Co-authored-by: Piotr Idzik <65706193+vil02@users.noreply.github.com>
1 parent 26c2465 commit 12b6c29

File tree

3 files changed

+124
-62
lines changed

3 files changed

+124
-62
lines changed

‎src/main/java/com/thealgorithms/dynamicprogramming/DyanamicProgrammingKnapsack.java

Lines changed: 0 additions & 36 deletions
This file was deleted.

‎src/main/java/com/thealgorithms/dynamicprogramming/Knapsack.java

Lines changed: 43 additions & 26 deletions
Original file line numberDiff line numberDiff line change
@@ -1,38 +1,55 @@
11
package com.thealgorithms.dynamicprogramming;
22

3+
import java.util.Arrays;
4+
35
/**
4-
* A DynamicProgramming based solution for 0-1 Knapsack problem
6+
* A Dynamic Programming based solution for the 0-1 Knapsack problem.
7+
* This class provides a method, `knapSack`, that calculates the maximum value that can be
8+
* obtained from a given set of items with weights and values, while not exceeding a
9+
* given weight capacity.
10+
*
11+
* @see <a href="https://en.wikipedia.org/?title=0-1_Knapsack_problem">0-1 Knapsack Problem </a>
512
*/
6-
public class Knapsack {
13+
public final class Knapsack {
14+
15+
private Knapsack() {
16+
}
717

8-
private static int knapSack(int W, int[] wt, int[] val, int n) throws IllegalArgumentException {
9-
if (wt == null || val == null) {
10-
throw new IllegalArgumentException();
18+
private static void throwIfInvalidInput(final int weightCapacity, final int[] weights, final int[] values) {
19+
if (weightCapacity < 0) {
20+
throw new IllegalArgumentException("Weight capacity should not be negative.");
1121
}
12-
int i, w;
13-
int[][] rv = new int[n + 1][W + 1]; // rv means return value
14-
15-
// Build table rv[][] in bottom up manner
16-
for (i = 0; i <= n; i++) {
17-
for (w = 0; w <= W; w++) {
18-
if (i == 0 || w == 0) {
19-
rv[i][w] = 0;
20-
} else if (wt[i - 1] <= w) {
21-
rv[i][w] = Math.max(val[i - 1] + rv[i - 1][w - wt[i - 1]], rv[i - 1][w]);
22-
} else {
23-
rv[i][w] = rv[i - 1][w];
22+
if (weights == null || values == null || weights.length != values.length) {
23+
throw new IllegalArgumentException("Input arrays must not be null and must have the same length.");
24+
}
25+
if (Arrays.stream(weights).anyMatch(w -> w <= 0)) {
26+
throw new IllegalArgumentException("Input array should not contain non-positive weight(s).");
27+
}
28+
}
29+
30+
/**
31+
* Solves the 0-1 Knapsack problem using Dynamic Programming.
32+
*
33+
* @param weightCapacity The maximum weight capacity of the knapsack.
34+
* @param weights An array of item weights.
35+
* @param values An array of item values.
36+
* @return The maximum value that can be obtained without exceeding the weight capacity.
37+
* @throws IllegalArgumentException If the input arrays are null or have different lengths.
38+
*/
39+
public static int knapSack(final int weightCapacity, final int[] weights, final int[] values) throws IllegalArgumentException {
40+
throwIfInvalidInput(weightCapacity, weights, values);
41+
42+
// DP table to store the state of the maximum possible return for a given weight capacity.
43+
int[] dp = new int[weightCapacity + 1];
44+
45+
for (int i = 0; i < values.length; i++) {
46+
for (int w = weightCapacity; w > 0; w--) {
47+
if (weights[i] <= w) {
48+
dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
2449
}
2550
}
2651
}
2752

28-
return rv[n][W];
29-
}
30-
31-
// Driver program to test above function
32-
public static void main(String[] args) {
33-
int[] val = new int[] {50, 100, 130};
34-
int[] wt = new int[] {10, 20, 40};
35-
int W = 50;
36-
System.out.println(knapSack(W, wt, val, val.length));
53+
return dp[weightCapacity];
3754
}
3855
}

‎src/test/java/com/thealgorithms/dynamicprogramming/KnapsackTest.java

Lines changed: 81 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,81 @@
1+
package com.thealgorithms.dynamicprogramming;
2+
3+
import static org.junit.jupiter.api.Assertions.assertEquals;
4+
import static org.junit.jupiter.api.Assertions.assertThrows;
5+
6+
import org.junit.jupiter.api.Test;
7+
8+
public class KnapsackTest {
9+
@Test
10+
public void testKnapSackBasic() {
11+
int[] weights = {2, 3, 4, 5};
12+
int[] values = {3, 4, 5, 6};
13+
int weightCapacity = 5;
14+
int expected = 7; // Maximum value should be 7 (items 1 and 4).
15+
int result = Knapsack.knapSack(weightCapacity, weights, values);
16+
assertEquals(expected, result);
17+
}
18+
19+
@Test
20+
public void testKnapSackEmpty() {
21+
int[] weights = {};
22+
int[] values = {};
23+
int weightCapacity = 10;
24+
int expected = 0; // With no items, the result should be 0.
25+
int result = Knapsack.knapSack(weightCapacity, weights, values);
26+
assertEquals(expected, result);
27+
}
28+
29+
@Test
30+
public void testKnapSackNoCapacity() {
31+
int[] weights = {2, 3, 4};
32+
int[] values = {3, 4, 5};
33+
int weightCapacity = 0;
34+
int expected = 0; // With no capacity, the result should be 0.
35+
int result = Knapsack.knapSack(weightCapacity, weights, values);
36+
assertEquals(expected, result);
37+
}
38+
39+
@Test
40+
public void testKnapSackMaxCapacity() {
41+
int[] weights = {2, 3, 4, 5};
42+
int[] values = {3, 4, 5, 6};
43+
int weightCapacity = 10;
44+
int expected = 13; // Maximum value should be 13 (items 1, 3, and 4).
45+
int result = Knapsack.knapSack(weightCapacity, weights, values);
46+
assertEquals(expected, result);
47+
}
48+
49+
@Test
50+
public void testKnapSackThrowsForInputsOfDifferentLength() {
51+
int[] weights = {2, 3, 4};
52+
int[] values = {3, 4, 5, 6}; // Different length values array.
53+
int weightCapacity = 5;
54+
assertThrows(IllegalArgumentException.class, () -> { Knapsack.knapSack(weightCapacity, weights, values); });
55+
}
56+
57+
@Test
58+
public void testKnapSackThrowsForNullInputs() {
59+
int[] weights = {2, 3, 4};
60+
int[] values = {3, 4, 6};
61+
int weightCapacity = 5;
62+
assertThrows(IllegalArgumentException.class, () -> { Knapsack.knapSack(weightCapacity, null, values); });
63+
assertThrows(IllegalArgumentException.class, () -> { Knapsack.knapSack(weightCapacity, weights, null); });
64+
}
65+
66+
@Test
67+
public void testKnapSackThrowsForNegativeCapacity() {
68+
int[] weights = {2, 3, 4, 5};
69+
int[] values = {3, 4, 5, 6};
70+
int weightCapacity = -5;
71+
assertThrows(IllegalArgumentException.class, () -> { Knapsack.knapSack(weightCapacity, weights, values); });
72+
}
73+
74+
@Test
75+
public void testKnapSackThrowsForNegativeWeight() {
76+
int[] weights = {2, 0, 4};
77+
int[] values = {3, 4, 6};
78+
int weightCapacity = 5;
79+
assertThrows(IllegalArgumentException.class, () -> { Knapsack.knapSack(weightCapacity, weights, values); });
80+
}
81+
}

0 commit comments

Comments
 (0)