Problem
You are given arraysweights and values, where each index represents an item. You are also given an integer capacity representing the maximum weight the knapsack can hold.
Return the maximum total value that can be obtained without exceeding the given capacity. Each item can either be included once or excluded. This is why it is called the 0/1 Knapsack problem.
Example(s)
Consider the following example(s) to understand the expected input and output.Input
weights = [1, 3, 4, 5]
values = [1, 4, 5, 7]
capacity = 7
Output
9Solution(s)
Memoization Approach
We start from the first item and decide whether to include or exclude the current item. If the current item's weight is greater than the remaining capacity, we cannot include it, so we move to the next item.Otherwise, we have two choices. We can include the current item, adding its value and reducing the remaining capacity, or exclude it and keep the same capacity.
We take the maximum value from these two choices. The same combination of
index and remaining capacity can be reached multiple times, so we store the result in a memoization table.
class Solution {
public int knapsack(int W, int val[], int wt[]) {
int n = wt.length;
int[][] memo = new int[n][W + 1];
for (int i = 0; i < n; i++) {
Arrays.fill(memo[i], -1);
}
return sack(0, W, val, wt, memo);
}
private int sack(int index, int w, int val[], int wt[], int[][] memo) {
// No items left or no capacity remaining.
if (index == wt.length || w == 0) {
return 0;
}
// Return the cached result.
if (memo[index][w] != -1) {
return memo[index][w];
}
// Current item does not fit.
if (w < wt[index]) {
return sack(index + 1, w, val, wt, memo);
}
// Include or exclude the current item.
return memo[index][w] = Math.max(
val[index] + sack(index + 1, w - wt[index], val, wt, memo),
sack(index + 1, w, val, wt, memo)
);
}
}
Complexity
There aren × W possible combinations of item index and remaining capacity, and each combination is calculated only once, resulting in O(n × W) time complexity.
The memoization table requires
O(n × W) space.
Tabulation Approach
We can also solve the problem using bottom-up Dynamic Programming.Let
dp[i][capacity] represent the maximum value that can be obtained using the first i items with the given capacity.
For each item, we have two choices. We can exclude it and keep the value from the previous row, or include it if the item's weight fits within the current capacity.
If we include the item, its value is added to the best value obtained using the remaining capacity.
class Solution {
public int knapsack(int[] weights, int[] values, int capacity) {
int n = weights.length;
int[][] dp = new int[n + 1][capacity + 1];
for (int i = 1; i <= n; i++) {
int weight = weights[i - 1];
int value = values[i - 1];
for (int currentCapacity = 1; currentCapacity <= capacity; currentCapacity++) {
// Exclude the current item.
dp[i][currentCapacity] = dp[i - 1][currentCapacity];
// Include the current item if it fits.
if (weight <= currentCapacity) {
dp[i][currentCapacity] = Math.max(dp[i][currentCapacity],
value + dp[i - 1][currentCapacity - weight]);
}
}
}
return dp[n][capacity];
}
}
Complexity
The DP table containsn × capacity states, and each state is calculated once, resulting in O(n × capacity) time complexity. The DP table requires O(n × capacity) space.
Space Optimized Approach
In the tabulation approach, each row only depends on the values from the previous row. Therefore, instead of storing the entire two-dimensional DP table, we can use a single array.The capacity must be processed from right to left. This ensures that each item is used only once. If we processed the capacity from left to right, the same item could be used multiple times, which would turn the problem into an Unbounded Knapsack problem.
class Solution {
public int knapsack(int[] weights, int[] values, int capacity) {
int[] dp = new int[capacity + 1];
for (int i = 0; i < weights.length; i++) {
// Process capacity from right to left.
for (int currentCapacity = capacity; currentCapacity >= weights[i]; currentCapacity--) {
dp[currentCapacity] = Math.max(dp[currentCapacity],
values[i] + dp[currentCapacity - weights[i]]);
}
}
return dp[capacity];
}
}
Complexity
Each item is processed for every possible capacity, resulting inO(n × capacity) time complexity. The one-dimensional DP array requires O(capacity) space.