Unbounded Knapsack & Coin Change

In our previous lessons on dynamic programming, we established a powerful template for solving 0/1 Knapsack and its variations, like Subset Sum. The cornerstone of the space-optimized solution was a 1D DP array where the inner loop iterated backwards. This was a deliberate choice to ensure that each item was considered only once per subproblem.

Today, we're going to flip that logic on its head. We will explore what happens when we intentionally allow an item to be used multiple times. This brings us to the Unbounded Knapsack pattern. You'll learn how a simple change in the loop's direction unlocks a whole new class of problems. Our goal is to formulate the recurrence for Unbounded Knapsack and apply this powerful pattern to solve the classic Coin Change problem, a frequent flyer in coding interviews.

From 0/1 to Unbounded: A Single Rule Change

The Unbounded Knapsack problem is nearly identical to its 0/1 counterpart: given items with weights and values, and a knapsack with a maximum capacity, find the maximum value of items that can be carried. The only difference is a crucial one: you have an infinite supply of each item.

This seemingly small change has a profound impact on the decision-making process.

Formulating the Recurrence

How do we adapt our "take it or leave it" logic to handle infinite items? There are two intuitive ways to think about this, both leading to the same DP solution. A great video from the "Inside code" channel explores these recursive approaches.

As the video explains, the second recursive approach only depends on one changing parameter: the remaining capacity k. This means we can use memoization with a 1D array, where dp[k] stores the optimal result for capacity k. This sets the stage for a bottom-up DP solution.

The 1D DP Solution: The Forward Loop

In the last lesson, we stressed the importance of a backward loop for the 1D array in 0/1 Knapsack. Now, we do the opposite. For Unbounded Knapsack, we use a forward loop. This is the critical implementation detail that enables item reuse.

Let's understand exactly why this works.

To solidify this, let's trace a simple example: weights = [1, 2], values = [10, 25], Capacity = 3. Our DP array is dp = [0, 0, 0, 0].

1. Outer loop: item = {weight: 1, value: 10}

   • Inner loop (forward): w from 1 to 3.
   • w = 1: dp[1] = max(dp[1], dp[0] + 10) = 10
   • w = 2: dp[2] = max(dp[2], dp[1] + 10) = 20 (used item 1 twice)
   • w = 3: dp[3] = max(dp[3], dp[2] + 10) = 30 (used item 1 thrice)
   • After this pass, dp = [0, 10, 20, 30].

2. Outer loop: item = {weight: 2, value: 25}

   • Inner loop (forward): w from 2 to 3.
   • w = 2: dp[2] = max(dp[2], dp[0] + 25) = max(20, 25) = 25
   • w = 3: dp[3] = max(dp[3], dp[1] + 25) = max(30, 10 + 25) = 35
   • Final dp = [0, 10, 25, 35]. The max value is 35.

The general implementation for the Unbounded Knapsack problem is therefore very clean.

Application: The Coin Change Problem

Now, let's apply this pattern to a problem where the "knapsack" is less obvious.

Problem: Given an array of coin denominations and a total amount, find the fewest number of coins required to make up that amount. Assume an infinite supply of each coin.

This is a classic Unbounded Knapsack problem in disguise:

• Items: The coins.
• Weights: The face value of each coin (e.g., 1, 2, 5).
• Values: The "value" of each coin is simply 1, because we are trying to minimize the count of coins.
• Knapsack Capacity: The target amount.
• Goal: Instead of maximizing value, we aim to minimize the total "value" (the coin count) to perfectly match the capacity.

The NeetCode channel has an excellent video that breaks this problem down. It starts by showing why a simple greedy approach fails and then builds the DP solution from the ground up.

The recurrence relation for Coin Change is:

for every coin c that is less than or equal to the current amount a. Here, dp[a] stores the minimum coins needed for amount a.

Here is a Python implementation based on this logic:

def coin_change(coins: list[int], amount: int) -> int:
    # Initialize dp array. amount + 1 serves as our "infinity".
    # The size is amount + 1 to handle amounts from 0 to 'amount'.
    dp = [amount + 1] * (amount + 1)
    
    # Base case: 0 coins are needed to make an amount of 0.
    dp[0] = 0
    
    # Iterate through all amounts from 1 up to the target amount.
    for a in range(1, amount + 1):
        # For each amount, try every coin.
        for c in coins:
            if a - c >= 0:
                # This is the core recurrence relation.
                # We are seeing if using coin 'c' gives a better (smaller) result.
                dp[a] = min(dp[a], 1 + dp[a - c])

    # If dp[amount] is still our "infinity" value, it was not possible to make the amount.
    return dp[amount] if dp[amount] != amount + 1 else -1

# Example from the video
coins1 = [1, 3, 4] # Note: video uses [1,3,4,5] for the example, but this is a clearer case
amount1 = 7
print(f"Min coins for amount {amount1} with {coins1}: {coin_change(coins1, amount1)}") # Output: 2 (3 + 4)

coins2 = [2]
amount2 = 3
print(f"Min coins for amount {amount2} with {coins2}: {coin_change(coins2, amount2)}") # Output: -1

Conclusion

In this lesson, we demystified the Unbounded Knapsack pattern and saw its direct connection to the 0/1 Knapsack. By understanding the underlying data dependencies, you can now confidently solve both using a 1D DP array, armed with the knowledge of when to loop forwards versus backwards.

Key Takeaways:

• Unbounded vs. 0/1: The core difference is the ability to reuse items. This is often signaled by phrases like "infinite supply" or the absence of usage constraints.
• The Forward Loop: When implementing a 1D DP solution for Unbounded Knapsack problems, the inner loop over the capacity/amount must iterate forwards. This allows the DP state to reflect the use of an item multiple times.
• Recurrence Relation: The general recurrence for Unbounded Knapsack is dp[w] = op(dp[w], value[i] + dp[w - weight[i]]), where op can be max, min, or + depending on whether you are maximizing, minimizing, or counting.
• Pattern Recognition: Problems like Coin Change, Rod Cutting, and others can be modeled as Unbounded Knapsack problems by correctly identifying the "items," "weights," "values," and "capacity."

We've now covered the two main variants of the knapsack problem. In our next lesson, we will move to a new category of DP problems that operate on two sequences, starting with the Longest Common Subsequence (LCS). This will introduce a 2D DP recurrence with a different structure and set of dependencies.