Skip to content
Tutorials Center
My learning

Topics

Lesson 152 of 225 ยท Dynamic Programming

Unbounded Knapsack and Coin Change

Solve coin change with dynamic programming in Python: fewest coins, counting ways, combinations vs permutations, rod cutting and unbounded knapsack.

In the 0/1 knapsack every item could be used at most once. Now remove that limit: you have an endless supply of each item. This is the unbounded knapsack, and its most famous special case is coin change: given coin values and a target amount, what is the fewest coins that make the amount, or in how many ways can you make it?

These problems look almost identical to 0/1 knapsack, and the difference comes down to a single detail: the direction of one loop. Getting that direction (and the order of two loops) right is the whole skill, and this lesson shows exactly why it matters.

Why greedy is not enough

With US coins [1, 5, 10, 25], taking the biggest coin that fits always works. With coins [1, 3, 4] and amount 6, greedy takes 4, then 1, then 1: three coins. But 3 + 3 uses only two. When the coin system is arbitrary, you must consider every choice, and that is a job for dynamic programming. (See greedy algorithms for when the greedy shortcut is safe.)

Python Greedy fails on [1, 3, 4]

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Minimum number of coins

Define the state. dp[a] = the fewest coins needed to make amount a.

Transition. The last coin used is some coin c. Before it, we had amount a - c. So:

TEXT
dp[a] = 1 + min(dp[a - c])   for every coin c <= a
dp[0] = 0                    (zero coins make zero)

Amounts that cannot be made stay at infinity. Here is the table for coins [1, 3, 4] and amount 6:

TEXT
amount:  0  1  2  3  4  5  6
dp:      0  1  2  1  1  2  2
                          ^ via 3 + 3 (dp[3] + 1)

Check dp[6]: try coin 1 (dp[5] + 1 = 3), coin 3 (dp[3] + 1 = 2), coin 4 (dp[2] + 1 = 3). The minimum is 2.

Brute force first

The plain recursion tries every coin at every step. It is correct but explodes, because the same amounts are recomputed over and over (the classic overlapping subproblems).

Python Brute-force recursion counts its calls

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The number of calls grows roughly exponentially in the amount. Memoization fixes that by remembering each answer.

Bottom-up table

The tabulated version fills amounts from 0 upward. Each amount looks at every coin, so the cost is O(amount x number of coins) time and O(amount) space.

Python Minimum coins with a DP table

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Do not use 0 as the "impossible" marker. Zero already means "zero coins". Use infinity (or amount + 1) and convert to -1 only at the very end.

Reconstructing the coins

Store, for every amount, which coin gave the best answer, then walk backwards from the target.

Python Recover which coins were used

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Counting the ways

Now ask a different question: how many different ways can you make the amount? Define ways[a] as the number of ways to make a. The base case is ways[0] = 1: there is exactly one way to make zero, which is to take nothing.

The tempting recurrence ways[a] = sum(ways[a - c]) over all coins is not the same as counting combinations. It counts ordered sequences, so 1 + 3 and 3 + 1 are two different ways. Whether that is what you want depends on the problem, and the loop order decides it.

Combinations: coins on the outside

Python
for coin in coins:                 # outer: one coin at a time
    for a in range(coin, amount + 1):
        ways[a] += ways[a - coin]

Process coins one at a time. After handling coin c, ways[a] counts the ways using only the coins seen so far, and because coins are added in a fixed order, 1 + 3 and 3 + 1 can never both appear. This counts combinations (order does not matter).

Permutations: amounts on the outside

Python
for a in range(1, amount + 1):     # outer: one amount at a time
    for coin in coins:
        if coin <= a:
            ways[a] += ways[a - coin]

At each amount, any coin may be the last one placed, so different orders are counted separately. This counts permutations (ordered sequences, like climbing stairs with steps of 1, 3 and 4).

Python Combinations vs permutations

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For amount 6 and coins [1, 3, 4], the combinations are 1x6, 1x3 + 3, 3 + 3, and 1x2 + 4: four ways. The permutations also count each rearrangement, such as 1,1,4, 1,4,1 and 4,1,1, so the number is larger (9 for amount 6).

Unbounded vs 0/1: the direction of the loop

Compare the one-dimensional space-optimised tables:

TEXT
0/1 knapsack:   for w from capacity DOWN to weight   (each item once)
unbounded:      for w from weight UP to capacity     (item may repeat)

Going upward, dp[w - weight] has already been updated in this same pass, so it may already include the current item, which is exactly "use it again". Going downward, dp[w - weight] is still the old value, so the item is used at most once. One flipped loop converts one problem into the other.

Unbounded knapsack and rod cutting

Unbounded knapsack: items have a weight and a value, you can take any number of each, and you maximise value within a capacity. The recurrence is dp[w] = max(dp[w], dp[w - weight] + value) with w going upward.

Rod cutting is the same problem: a rod of length n can be cut into integer pieces, each length has a price, and you maximise total price. A piece of length L is an item with weight L and value price[L].

Python Unbounded knapsack and rod cutting

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Both run in O(capacity x items) time and O(capacity) space.

Common mistakes

  • Using greedy on a coin system you have not proven canonical.
  • Initialising impossible amounts to 0 instead of infinity.
  • Swapping the loop order when counting: coins outside gives combinations, amounts outside gives permutations.
  • Forgetting ways[0] = 1, which makes every count zero.
  • Reading dp[a - coin] with coin > a, which wraps to a negative index in Python and silently reads the wrong cell. Always guard with coin <= a.
  • Recursion depth: a memoized recursion on a big amount with coin 1 goes amount levels deep and can hit the recursion limit. Prefer the table.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why does greedy fail for coins [1, 3, 4] and amount 6?

    Always taking the biggest coin that fits is not safe for arbitrary coin systems. DP tries every last coin and finds 3 + 3.
  2. 2. What is the time complexity of the bottom-up minimum-coins table for amount A and n coins?

    There are A + 1 table cells, and each one tries up to n coins.
  3. 3. To count combinations (order does not matter) of coins that sum to an amount, which loop is on the outside?

    With the coins outside, each coin is added in a fixed order, so 1 + 3 and 3 + 1 are never counted separately. With the amounts outside you count ordered sequences.
  4. 4. In the one-dimensional unbounded knapsack, why does the weight loop run upward?

    An upward pass reads values already updated in the same pass, which is exactly what allows an item to be taken again. A downward pass gives 0/1 behavior.
  5. 5. What should ways[0] be when counting the ways to make an amount?

    There is exactly one way to make zero: choose nothing. With ways[0] = 0, every count would stay zero.

Summary

  • Unbounded knapsack allows unlimited copies of each item; coin change and rod cutting are special cases.
  • Minimum coins: dp[a] = 1 + min(dp[a - c]), with dp[0] = 0 and infinity for unreachable amounts. Time O(amount x coins), space O(amount).
  • Counting ways: ways[0] = 1. Coins outside the loop gives combinations; amounts outside gives permutations.
  • Flip the capacity loop from downward (0/1) to upward (unbounded) to allow reuse.
  • Store the chosen coin per amount to reconstruct the answer.
  • Greedy works only for special coin systems; DP works for all.

Next: Longest Increasing Subsequence