The knapsack problem is a combinatorial optimization problem that is NP-complete. It involves a set of n items and a knapsack with a maximum weight capacity of w. Each item has its own weight and value. The goal is to determine which items to include in the knapsack to maximize the total value without exceeding the weight limit.
If each item can be selected either 0 or 1 time, the problem is called the 0-1 knapsack problem. If there is no restriction on the number of each item that can be selected, the problem is called the unbounded knapsack problem or the complete knapsack problem.
0-1 Knapsack Problem
The knapsack problem can be solved using dynamic programming. Taking the 0-1 knapsack problem as an example, we can define a 2D array dp to store the maximum value, where dp[i][j] represents the maximum value achievable with the first i items and a knapsack capacity of j.
When we consider the i-th item, for the current knapsack capacity j, there are two choices:
- Do not include the i-th item: In this case, dp[i][j] = dp[i-1][j], meaning the maximum value is the same as that of the first i-1 items.
- Include the i-th item: If the i-th item is included, and its weight is weight and value is value, then dp[i][j] = dp[i-1][j – weight] + value.
During the traversal, we simply take the maximum of these two choices. The time complexity and space complexity of this approach are both O(nw), where n is the number of items and w is the knapsack’s capacity.
Template for 0-1 knapsack problem (Python):
def knapsack(weights: List[int], values: List[int], n: int, w: int) -> int:
dp = [[0 for _ in range(w + 1)] for _ in range(n + 1)]
for i in range(1, n + 1):
weight, value = weights[i - 1], values[i - 1]
for j in range(1, w + 1):
if j >= weight:
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight] + value)
else:
dp[i][j] = dp[i - 1][j]
return dp[n][w]Improved (Optimize the space complexity ) templare for 0-1 knapsack problem (Python):
We can further optimize the space complexity of the 0-1 knapsack problem to O(w), where w is the knapsack’s capacity. Suppose we are currently considering item i = 2, with a weight = 2 and value = 3. For a knapsack capacity j, we can compute:
Here, we observe that the calculation for dp[2][j] only depends on the information from the previous row (i = 1). This means that once we have processed the previous row, we no longer need the data from earlier rows. Therefore, we can eliminate the first dimension of the dp matrix and update the array in place. When considering item i, the update rule becomes:
However, it is crucial to traverse the dp array in reverse order (from right to left) when updating it. This ensures that when we compute dp[j], the value of dp[j – weight] still corresponds to the state from the previous row (i-1). If we traverse from left to right (forward order), dp[j – weight] might have already been updated to reflect the current item i, leading to incorrect results.
def knapsack(weights: List[int], values: List[int], n: int, w: int) -> int:
dp = [0] * (w + 1)
for i in range(1, n + 1):
weight, value = weights[i - 1], values[i - 1]
for j in range(w, weight - 1, -1):
dp[j] = max(dp[j], [j - weight] + value)
return dp[w]Complete Knapsack Problem
In the unbounded knapsack problem, an item can be selected multiple times. Suppose we are considering item i = 2, with a weight = 2 and value = 3. For a knapsack capacity j = 5, at most 2 of this item can be included. In this case, our state transition equation becomes:
If we use this approach, assuming the knapsack capacity is infinitely large and the item’s weight is infinitely small, the number of comparisons would also approach infinity, far exceeding the O(nw) time complexity.
To solve this, we observe that when computing dp[2][3], we have already considered the cases of dp[1][3] and dp[2][1], and when computing dp[2][1], we have already considered the case of dp[1][1]. Therefore, for the scenario of selecting multiple items, we only need to consider dp[2][3]. That is:
This leads us to the state transition equation for the unbounded knapsack problem:
The only difference between this and the 0-1 knapsack problem is that the second term in the state transition equation changes from dp[i-1][j – w] to dp[i][j – w]. This small adjustment allows us to account for the possibility of selecting the same item multiple times.
Template for complete knapsack problem (Python):
def knapsack(weights: List[int], values: List[int], n: int, w: int) -> int:
dp = [[0 for _ in range(w + 1)] for _ in range(n + 1)]
for i in range(1, n + 1):
weight, value = weights[i - 1], values[i - 1]
for j in range(1, w + 1):
if j >= weight:
dp[i][j] = max(dp[i - 1][j], dp[i][j - weight] + value)
else:
dp[i][j] = dp[i - 1][j]
return dp[n][w]Improved (Optimize the space complexity ) templare for complete knapsack problem (Python):
Similarly, we can also reduce the space complexity to O(w) by using space optimization. Here, it is important to note that we must traverse each row in forward order because we need to utilize the information of the current item at the j – weight column.
def knapsack(weights: List[int], values: List[int], n: int, w: int) -> int:
dp = [0] * (w + 1)
for i in range(1, n + 1):
weight, value = weights[i - 1], values[i - 1]
for j in range(weight, w + 1):
dp[j] = max(dp[j], [j - weight] + value)
return dp[w]