Content-Length: 767689 | pFad | http://github.com/TheAlgorithms/Java/commit/cfd784105bbb47b172c0ba65b46bd30700953c9f

C3 Feat(Improved): Add 0/1 Knapsack Problem: Recursive and Tabulation (B… · TheAlgorithms/Java@cfd7841 · GitHub
Skip to content

Commit cfd7841

Browse files
o000SAI000oalxkm
o000SAI000o
and
alxkm
authored
Feat(Improved): Add 0/1 Knapsack Problem: Recursive and Tabulation (Bottom-Up DP) Implementations in Java along with their corresponding Tests (#6425)
* feat: Add 0/1 Knapsack and its tabulation implementation with their corresponding tests * feat: Add 0/1 Knapsack and its tabulation implementation with their corresponding tests * feat: Add 0/1 Knapsack and its tabulation implementation with their corresponding tests * Feat:add 0/1knapsack and 0/1knapsacktabulation along with their tests * Feat:add 0/1knapsack and 0/1knapsacktabulation along with their tests * Feat:add 0/1knapsack and 0/1knapsacktabulation along with their tests --------- Co-authored-by: Oleksandr Klymenko <alexanderklmn@gmail.com>
1 parent bbbc1dd commit cfd7841

File tree

4 files changed

+268
-0
lines changed

4 files changed

+268
-0
lines changed

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

Lines changed: 53 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,53 @@
1+
package com.thealgorithms.dynamicprogramming;
2+
3+
/**
4+
* The {@code KnapsackZeroOne} provides Recursive solution for the 0/1 Knapsack
5+
* problem. Solves by exploring all combinations of items using recursion. No
6+
* memoization or dynamic programming optimizations are applied.
7+
*
8+
* Time Complexity: O(2^n) — explores all subsets.
9+
* Space Complexity: O(n) — due to recursive call stack.
10+
*
11+
* Problem Reference: https://en.wikipedia.org/wiki/Knapsack_problem
12+
*/
13+
public final class KnapsackZeroOne {
14+
15+
private KnapsackZeroOne() {
16+
// Prevent instantiation
17+
}
18+
19+
/**
20+
* Solves the 0/1 Knapsack problem using recursion.
21+
*
22+
* @param values the array containing values of the items
23+
* @param weights the array containing weights of the items
24+
* @param capacity the total capacity of the knapsack
25+
* @param n the number of items
26+
* @return the maximum total value achievable within the given weight limit
27+
* @throws IllegalArgumentException if input arrays are null, empty, or
28+
* lengths mismatch
29+
*/
30+
public static int compute(final int[] values, final int[] weights, final int capacity, final int n) {
31+
if (values == null || weights == null) {
32+
throw new IllegalArgumentException("Input arrays cannot be null.");
33+
}
34+
if (values.length != weights.length) {
35+
throw new IllegalArgumentException("Value and weight arrays must be of the same length.");
36+
}
37+
if (capacity < 0 || n < 0) {
38+
throw new IllegalArgumentException("Invalid input: arrays must be non-empty and capacity/n "
39+
+ "non-negative.");
40+
}
41+
if (n == 0 || capacity == 0 || values.length == 0) {
42+
return 0;
43+
}
44+
45+
if (weights[n - 1] <= capacity) {
46+
final int include = values[n - 1] + compute(values, weights, capacity - weights[n - 1], n - 1);
47+
final int exclude = compute(values, weights, capacity, n - 1);
48+
return Math.max(include, exclude);
49+
} else {
50+
return compute(values, weights, capacity, n - 1);
51+
}
52+
}
53+
}

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

Lines changed: 69 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,69 @@
1+
package com.thealgorithms.dynamicprogramming;
2+
3+
/**
4+
* Tabulation (Bottom-Up) Solution for 0-1 Knapsack Problem.
5+
* This method uses dynamic programming to build up a solution iteratively,
6+
* filling a 2-D array where each entry dp[i][w] represents the maximum value
7+
* achievable with the first i items and a knapsack capacity of w.
8+
*
9+
* The tabulation approach is efficient because it avoids redundant calculations
10+
* by solving all subproblems in advance and storing their results, ensuring
11+
* each subproblem is solved only once. This is a key technique in dynamic programming,
12+
* making it possible to solve problems that would otherwise be infeasible due to
13+
* exponential time complexity in naive recursive solutions.
14+
*
15+
* Time Complexity: O(n * W), where n is the number of items and W is the knapsack capacity.
16+
* Space Complexity: O(n * W) for the DP table.
17+
*
18+
* For more information, see:
19+
* https://en.wikipedia.org/wiki/Knapsack_problem#Dynamic_programming
20+
*/
21+
public final class KnapsackZeroOneTabulation {
22+
23+
private KnapsackZeroOneTabulation() {
24+
// Prevent instantiation
25+
}
26+
27+
/**
28+
* Solves the 0-1 Knapsack problem using the bottom-up tabulation technique.
29+
* @param values the values of the items
30+
* @param weights the weights of the items
31+
* @param capacity the total capacity of the knapsack
32+
* @param itemCount the number of items
33+
* @return the maximum value that can be put in the knapsack
34+
* @throws IllegalArgumentException if input arrays are null, of different lengths,or if capacity or itemCount is invalid
35+
*/
36+
public static int compute(final int[] values, final int[] weights, final int capacity, final int itemCount) {
37+
if (values == null || weights == null) {
38+
throw new IllegalArgumentException("Values and weights arrays must not be null.");
39+
}
40+
if (values.length != weights.length) {
41+
throw new IllegalArgumentException("Values and weights arrays must be non-null and of same length.");
42+
}
43+
if (capacity < 0) {
44+
throw new IllegalArgumentException("Capacity must not be negative.");
45+
}
46+
if (itemCount < 0 || itemCount > values.length) {
47+
throw new IllegalArgumentException("Item count must be between 0 and the length of the values array.");
48+
}
49+
50+
final int[][] dp = new int[itemCount + 1][capacity + 1];
51+
52+
for (int i = 1; i <= itemCount; i++) {
53+
final int currentValue = values[i - 1];
54+
final int currentWeight = weights[i - 1];
55+
56+
for (int w = 1; w <= capacity; w++) {
57+
if (currentWeight <= w) {
58+
final int includeItem = currentValue + dp[i - 1][w - currentWeight];
59+
final int excludeItem = dp[i - 1][w];
60+
dp[i][w] = Math.max(includeItem, excludeItem);
61+
} else {
62+
dp[i][w] = dp[i - 1][w];
63+
}
64+
}
65+
}
66+
67+
return dp[itemCount][capacity];
68+
}
69+
}

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

Lines changed: 78 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,78 @@
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 KnapsackZeroOneTabulationTest {
9+
10+
@Test
11+
public void basicCheck() {
12+
int[] values = {60, 100, 120};
13+
int[] weights = {10, 20, 30};
14+
int capacity = 50;
15+
int itemCount = values.length;
16+
17+
int expected = 220; // Best choice: item 1 (100) and item 2 (120)
18+
int result = KnapsackZeroOneTabulation.compute(values, weights, capacity, itemCount);
19+
assertEquals(expected, result);
20+
}
21+
22+
@Test
23+
public void emptyKnapsack() {
24+
int[] values = {};
25+
int[] weights = {};
26+
int capacity = 50;
27+
int itemCount = 0;
28+
29+
assertEquals(0, KnapsackZeroOneTabulation.compute(values, weights, capacity, itemCount));
30+
}
31+
32+
@Test
33+
public void zeroCapacity() {
34+
int[] values = {60, 100, 120};
35+
int[] weights = {10, 20, 30};
36+
int capacity = 0;
37+
int itemCount = values.length;
38+
39+
assertEquals(0, KnapsackZeroOneTabulation.compute(values, weights, capacity, itemCount));
40+
}
41+
42+
@Test
43+
public void negativeCapacity() {
44+
int[] values = {10, 20, 30};
45+
int[] weights = {1, 1, 1};
46+
int capacity = -10;
47+
int itemCount = values.length;
48+
49+
IllegalArgumentException exception = assertThrows(IllegalArgumentException.class, () -> KnapsackZeroOneTabulation.compute(values, weights, capacity, itemCount));
50+
assertEquals("Capacity must not be negative.", exception.getMessage());
51+
}
52+
53+
@Test
54+
public void mismatchedLengths() {
55+
int[] values = {60, 100}; // Only 2 values
56+
int[] weights = {10, 20, 30}; // 3 weights
57+
int capacity = 50;
58+
int itemCount = 2; // Matches `values.length`
59+
60+
// You could either expect 0 or throw an IllegalArgumentException in your compute function
61+
assertThrows(IllegalArgumentException.class, () -> { KnapsackZeroOneTabulation.compute(values, weights, capacity, itemCount); });
62+
}
63+
64+
@Test
65+
public void nullInputs() {
66+
int[] weights = {1, 2, 3};
67+
int capacity = 10;
68+
int itemCount = 3;
69+
70+
IllegalArgumentException exception1 = assertThrows(IllegalArgumentException.class, () -> KnapsackZeroOneTabulation.compute(null, weights, capacity, itemCount));
71+
assertEquals("Values and weights arrays must not be null.", exception1.getMessage());
72+
73+
int[] values = {1, 2, 3};
74+
75+
IllegalArgumentException exception2 = assertThrows(IllegalArgumentException.class, () -> KnapsackZeroOneTabulation.compute(values, null, capacity, itemCount));
76+
assertEquals("Values and weights arrays must not be null.", exception2.getMessage());
77+
}
78+
}

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

Lines changed: 68 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,68 @@
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+
class KnapsackZeroOneTest {
9+
10+
@Test
11+
void basicCheck() {
12+
int[] values = {60, 100, 120};
13+
int[] weights = {10, 20, 30};
14+
int capacity = 50;
15+
int expected = 220;
16+
17+
int result = KnapsackZeroOne.compute(values, weights, capacity, values.length);
18+
assertEquals(expected, result);
19+
}
20+
21+
@Test
22+
void zeroCapacity() {
23+
int[] values = {10, 20, 30};
24+
int[] weights = {1, 1, 1};
25+
int capacity = 0;
26+
27+
int result = KnapsackZeroOne.compute(values, weights, capacity, values.length);
28+
assertEquals(0, result);
29+
}
30+
31+
@Test
32+
void zeroItems() {
33+
int[] values = {};
34+
int[] weights = {};
35+
int capacity = 10;
36+
37+
int result = KnapsackZeroOne.compute(values, weights, capacity, 0);
38+
assertEquals(0, result);
39+
}
40+
41+
@Test
42+
void weightsExceedingCapacity() {
43+
int[] values = {10, 20};
44+
int[] weights = {100, 200};
45+
int capacity = 50;
46+
47+
int result = KnapsackZeroOne.compute(values, weights, capacity, values.length);
48+
assertEquals(0, result);
49+
}
50+
51+
@Test
52+
void throwsOnNullArrays() {
53+
assertThrows(IllegalArgumentException.class, () -> KnapsackZeroOne.compute(null, new int[] {1}, 10, 1));
54+
assertThrows(IllegalArgumentException.class, () -> KnapsackZeroOne.compute(new int[] {1}, null, 10, 1));
55+
}
56+
57+
@Test
58+
void throwsOnMismatchedArrayLengths() {
59+
assertThrows(IllegalArgumentException.class, () -> KnapsackZeroOne.compute(new int[] {10, 20}, new int[] {5}, 15, 2));
60+
}
61+
62+
@Test
63+
void throwsOnNegativeInputs() {
64+
assertThrows(IllegalArgumentException.class, () -> KnapsackZeroOne.compute(new int[] {10}, new int[] {5}, -1, 1));
65+
66+
assertThrows(IllegalArgumentException.class, () -> KnapsackZeroOne.compute(new int[] {10}, new int[] {5}, 5, -1));
67+
}
68+
}

0 commit comments

Comments
 (0)








ApplySandwichStrip

pFad - (p)hone/(F)rame/(a)nonymizer/(d)eclutterfier!      Saves Data!


--- a PPN by Garber Painting Akron. With Image Size Reduction included!

Fetched URL: http://github.com/TheAlgorithms/Java/commit/cfd784105bbb47b172c0ba65b46bd30700953c9f

Alternative Proxies:

Alternative Proxy

pFad Proxy

pFad v3 Proxy

pFad v4 Proxy