Knapsack Problems with DP

1. The 0/1 Knapsack Problem

Imagine you're a thief with a knapsack that can hold a maximum weight, say W. You enter a house with N items, each with a specific weight and value. Your goal is to choose which items to steal to maximize the total value, without exceeding your knapsack's weight limit. In the "0/1" version, for each item, you have two choices: take it (1) or don't take it (0). You cannot take a fraction of an item or take the same item multiple times.

Why a Greedy Approach Fails

Your first instinct might be a greedy one: "I'll just take the most valuable items first!" or "I'll take items with the best value-to-weight ratio!" While simple, these strategies don't guarantee the optimal solution. You might fill your bag with a high-value, heavy item, leaving no room for several lighter items that, combined, would have yielded a greater total value.

To see a concrete example of greedy failing, let's turn to a video that introduces the problem and this specific pitfall.

The Dynamic Programming Solution Path

Since greedy fails, we must explore all valid combinations and find the best one. This is a perfect use case for DP. We'll follow a standard progression: from a simple (but slow) recursive solution to a highly optimized one.

Step 1: Recursive Formulation (Top-Down)

The core of any DP solution is defining a function that solves a subproblem.

• State: Let's define f(index, capacity) as the maximum value we can obtain using items from 0 to index with a knapsack of the given capacity.
• Choices: At any index, we have two choices for the item:
  1. Not Take: We skip the item at index. The value is whatever we can get from the remaining items: f(index - 1, capacity).
  2. Take: We put the item at index in our knapsack. The value is value[index] plus whatever we can get from the remaining items with the reduced capacity: value[index] + f(index - 1, capacity - weight[index]). This choice is only possible if weight[index] <= capacity.
• Recurrence Relation: We want to maximize our value, so we take the best of these two choices:
  $f(\text{idx},\text{cap})=\max (\text{Not Take},\text{Take})$
• Base Case: If index is 0, we can only take that first item if its weight is less than or equal to the capacity. If capacity is 0 or we run out of items, we can't add any more value.

Step 2: Memoization, Tabulation, and Space Optimization

The pure recursive solution is exponential because it recomputes the same subproblems (e.g., f(5, 10)) many times. We can optimize this using DP. The following video resource will guide you through the entire process, from recursion to a final, space-optimized solution.

Summary of 0/1 Knapsack DP:

• Time Complexity: O(N * W), where N is the number of items and W is the capacity.
• Space Complexity:
  • Naive Tabulation: O(N * W)
  • Optimized: O(W)

The key takeaway for the O(W) space optimization is that when calculating the values for the current item i, we need the results from the previous item i-1. By iterating the capacity w from W down to 0, we ensure that when we compute dp[w], the value dp[w - weight[i]] is still from the previous iteration (row i-1), not the one we just updated in this iteration.

2. The Unbounded Knapsack Problem

The Unbounded Knapsack problem is a variation where you have an infinite supply of each item. You can pick any item as many times as you want, as long as you stay within the weight limit W.

Adapting the Recurrence Relation

The logic is almost identical to 0/1 Knapsack. The only difference is in the "Take" choice.

• State: f(index, capacity) remains the same.
• Choices:
  1. Not Take: Same as before. We move to the next item type. f(index - 1, capacity).
  2. Take: We take the item at index. The value is value[index] plus the best we can do with the remaining capacity. Since we have an infinite supply, we can potentially take this same item again. Therefore, we stay at the same index: value[index] + f(index, capacity - weight[index]).

This single change—f(index, ...) instead of f(index - 1, ...) in the "Take" case—is the only modification needed.

For a detailed walkthrough, let's refer to another excellent video.

Space Optimization for Unbounded Knapsack

As highlighted in the video and our test question above, the recurrence for Unbounded Knapsack is:
dp[i][w] = max(dp[i-1][w], value[i-1] + dp[i][w - weight[i-1]])

Notice the dp[i] on the right side of the max function. This means that to calculate the solution for the current item i and capacity w, we use results from the previous item (dp[i-1][w]) and results from the current item at a smaller capacity (dp[i][w - weight[i-1]]).

When we optimize to a single O(W) array, this translates perfectly to a forward loop (i.e., w from 0 to W). When we compute dp[w], we want to use the already-updated dp[w - weight[i-1]] from the current iteration, because that correctly models taking the same item more than once.

A clean Python implementation is also available in the article "Mastering the Unbounded Knapsack Problem" from AlgoCademy. You can see how the logic translates to a very concise 1D DP solution.

Conclusion

In this lesson, you've learned one of the most important dynamic programming patterns for coding interviews. The Knapsack problem family demonstrates how to make optimal choices under constraints.

Key Takeaways:

• Knapsack Pattern: Based on a "take" vs. "not take" choice for each item to maximize a value.
• State: The DP state is typically dp[index][capacity].
• 0/1 vs. Unbounded: The key difference is in the "Take" recursion:
  • 0/1: Move to the next item: f(index - 1, ...)
  • Unbounded: Stay at the same item: f(index, ...)
• Space Optimization (O(W)): This difference leads to a crucial implementation detail:
  • 0/1 Knapsack: Requires a backward capacity loop (W to 0) to use results from the previous row.
  • Unbounded Knapsack: Uses a forward capacity loop (0 to W) to use results from the current row.

Understanding these nuances is a strong signal in an interview that you have a deep grasp of dynamic programming.

Preview of the Next Lesson:

We will continue with this pattern in our next lesson, "Solve coin change problems using dynamic programming." The Coin Change 2 problem ("how many combinations of coins make a certain amount?") is a classic application of the Unbounded Knapsack pattern. This will give you more practice and help solidify your understanding.