cf.completefrontend
DYNAMIC PROGRAMMING · CORE

Unbounded knapsack

Build a total from pieces you may reuse as many times as you like, such as the fewest coins that make an amount.

Time O(amount × coins)Space O(amount)7 practice problemsStep-through picture

The idea

The unbounded knapsack is the knapsack where every kind of item comes in unlimited supply. The classic example is making change: with coins worth 1, 3, and 4, what is the fewest number of coins that adds up to 6?

Because items can be reused, the state only needs the amount left to build. One cell, fewest[total], answers "what is the fewest coins that add up to exactly total?" To fill it, try every coin as the last coin used, and look at the cell for what is left.

Greedy (always take the biggest coin that fits) can fail. For 6 with coins 1, 3, and 4, greedy takes 4 + 1 + 1, three coins, but 3 + 3 uses two. DP checks every option.

An everyday example

Paying exact postage with stamps

A parcel costs 6 to send and you have a sheet of 1, 3, and 4 stamps, as many of each as you like. You want to use as few stamps as possible. Work it out amount by amount: the fewest stamps for 1, for 2, for 3, and so on. For each amount, imagine the last stamp you stuck on, and use what you already know about the amount left over.

How the example maps to the code
In the exampleIn the code
The kinds of stampsThe coins array
The fewest stamps for an amountfewest[total]
Trying a stamp as the last onefor (const coin of coins)
The amount left after that stampfewest[total - coin]
Zero postage needs zero stampsfewest[0] = 0

From the slow way to unbounded knapsack

  1. Start with the greedy idea most people try first: keep taking the biggest coin that still fits. With coins 2, 5, and 6 and an amount of 10, it takes a 6, then a 2, then another 2: three coins. But two 5 coins make 10. Greedy commits to a coin before it knows what that coin leaves behind.
  2. So try every option instead. The fewest coins for total is one coin plus the fewest coins for whatever that coin leaves: 1 + fewest(total - coin), for the best coin. Written as plain recursion with coins 2, 5, and 6, this makes 5,411 calls for an amount of 30 and 90,060 calls for 40. The work grows by about 17 times for every 10 added to the amount.
  3. The calls repeat because the question only has one number in it: the amount left to build. However you got there, "the fewest coins for 4" has the same answer. With an amount of 40 there are only 41 different questions, from 0 to 40, but the recursion asks them 90,060 times.
  4. So make a table fewest with one cell per amount, from 0 to amount. Start with fewest[0] = 0 and every other cell at Infinity, meaning "not possible yet". Fill the totals from small to large, and for each total try every coin as the last coin. Because fewest[total - coin] may already use the same coin, coins can be reused as often as needed. That loop is the unbounded knapsack.

How it works

  1. Make fewest with amount + 1 cells, all Infinity, meaning "not possible yet".
  2. Set fewest[0] = 0: making 0 takes no coins.
  3. Loop total from 1 up to amount.
  4. For each coin that fits (coin <= total), the option is fewest[total - coin] + 1: the best way to make the rest, plus this coin.
  5. Keep the smallest option in fewest[total].
  6. At the end, fewest[amount] is the answer, or -1 if it is still Infinity.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function fewestCoins(coins, amount) {
  2. const fewest = new Array(amount + 1).fill(Infinity);
  3. fewest[0] = 0;
  4. for (let total = 1; total <= amount; total++) {
  5. for (const coin of coins) {
  6. if (coin <= total && fewest[total - coin] + 1 < fewest[total]) {
  7. fewest[total] = fewest[total - coin] + 1;
  8. }
  9. }
  10. }
  11. return fewest[amount] === Infinity ? -1 : fewest[amount];
  12. }

How fast it is

TimeO(amount × coins)
Extra memoryO(amount)

Every amount from 1 to amount tries every coin once. The table has one cell per amount.

  • Best caseO(amount × coins)

    Any input: every total from 1 to amount tries every coin, even after a one-coin answer has been found.

  • Average caseO(amount × coins)

    Any input: the work is set by the two loops, not by the coin values.

  • Worst caseO(amount × coins)

    The same. An impossible amount, like 3 with coins [2, 4], does the same amount of work and returns -1.

Common mistakes

  • Using greedy: biggest coin first. It fails for coins [1, 3, 4] and amount 6.
  • Starting the table at 0 instead of Infinity. Then Math.min always picks the fake 0 and every answer is wrong.
  • Returning Infinity instead of the agreed "impossible" value, such as -1.
  • Using the wrong loop order when counting ways, so 1 + 2 and 2 + 1 are counted twice when the question wants combinations.

When to use it

Look for these clues in a problem:

  • You can use each kind of item any number of times: coins, tile sizes, coupon types.
  • The question asks for the fewest pieces, the most value, or the number of ways to reach a total.
  • The total is a whole number of reasonable size, so a table with one cell per amount fits in memory.
  • A greedy rule (biggest piece first) seems right but you can find a case where it isn't.

Check yourself

Answer each one in your head first, then open it.

Why do the cells start at Infinity and not 0?

Because the code keeps the smallest option. A starting 0 would always be the smallest, so every cell would stay 0 and every answer would be wrong.

What part of the code lets a coin be used more than once?

Reading fewest[total - coin], which is the best for that smaller amount with all coins allowed. That answer may already include coin, so adding it again is reuse.

In the trace, why is fewest[3] still Infinity when a 2 coin fits?

The 2 coin leaves 1, and 1 can't be made from coins 2, 5, and 6. Infinity + 1 is Infinity, so the option never wins.

How many coin checks does it make for amount = 1000 and 4 coins?

4,000: each of the 1,000 totals checks each of the 4 coins once.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 7 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The table keeps one promise: when the loop starts on total, every cell from fewest[0] to fewest[total - 1] holds the true fewest coins for that amount, or Infinity if it can't be made. fewest[0] = 0 makes it true at the start.

Filling fewest[total] keeps the promise. Take any shortest list of coins that adds up to total, and look at its last coin, coin. The other coins add up to total - coin, and they must be a shortest list for that amount; otherwise swapping in a shorter list would make the whole thing shorter. So the true answer is fewest[total - coin] + 1 for some coin, and the code tries every coin and keeps the smallest. If no coin leads to a possible amount, every option is Infinity and the cell stays Infinity, which is also correct.

Reuse is allowed because fewest[total - coin] is the best for that smaller amount with every coin available, including coin itself. The order is by increasing total, and every coin is at least 1, so each cell only reads smaller cells that are already final. After the loop, the promise says fewest[amount] is the answer.

Going deeper

4 more ideas

What each cell of the table means

fewest[total] is the smallest number of coins whose values add up to exactly total. Infinity means no mix of coins makes that total. The table does not care which coins were used, only how many.

How much work it does

There are amount + 1 cells and each tries every coin, so the time is O(amount * coins). The table uses O(amount) space.

Counting combinations versus orders

To count ways, the loop order matters. If coins are the outer loop and totals the inner loop, 1 + 2 and 2 + 1 count once: you are counting combinations. If totals are the outer loop and coins the inner loop, they count separately: you are counting ordered sequences. Pick the order that matches the question.

How it differs from the 0/1 knapsack

In the 0/1 knapsack, taking an item reads the answer without that item (the row above). Here, taking a coin reads fewest[total - coin], which may itself already use the same coin. That is exactly what allows reuse.

Work it by hand

Every step in a table, with why

Find the fewest coins that make 10, using coins worth 2, 5, and 6 as many times as you like. Each row fills one cell of fewest.

coins = [2, 5, 6], amount = 10

SteptotalOptions tried (coin: count)fewest[total]What happensWhy
10-0Base caseMaking 0 takes no coins. Every other cell starts at Infinity.
21none fit∞ImpossibleEvery coin is bigger than 1, so the cell stays Infinity.
322: 11One 2 coinThe 2 coin leaves 0, which takes 0 coins, so the option is 0 + 1.
432: ∞∞Still impossibleThe 2 coin leaves 1, which is impossible, and Infinity + 1 is still Infinity. Odd totals below 5 can't be made.
542: 22Two 2 coinsThe 2 coin leaves 2, which takes one coin. Reusing the same coin is allowed.
652: ∞, 5: 11One 5 coinThe 2 coin leaves 3, which is impossible. The 5 coin alone does it.
762: 3, 5: ∞, 6: 11One 6 coinThree options, and the 6 coin wins with a single coin.
872: 2, 5: 2, 6: ∞2Tie: 5 + 2Both the 2 coin and the 5 coin give 2. The update on line 6 needs strictly fewer, so the first one found stays.
982: 2, 5: ∞, 6: 226 + 2 or 2 + 6Another tie: both orders of the same two coins.
1092: 3, 5: 3, 6: ∞3Three coinsFor example 5 + 2 + 2. The 6 coin leaves 3, which is impossible.
11102: 3, 5: 2, 6: 32Two 5 coins; loop endsThe 6 coin, which greedy would take first, gives 3. The 5 coin leaves 5, which takes one coin, so 2. Line 11 returns it.

It returns 2: two 5 coins. Greedy would return 3. The loop ends after total reaches amount, and the cell is not Infinity, so the answer is the number, not -1.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Unbounded knapsackO(amount × coins)O(amount)The default for fewest coins or counting ways when amount is a modest whole number.
Greedy, biggest coin firstO(n log n)O(1)Only for coin systems known to work with it, such as 1, 5, 10, 25. It fails for coins like 2, 5, and 6.
Breadth-first search over totalsO(amount × coins)O(amount)When the answer is likely small, since it stops at the first time it reaches amount.
Plain recursionO(2^n)O(n)Only to check the recurrence on amounts below about 20.

Extra memory: O(amount) for the fewest array. It does not grow with the number of coins.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Unbounded knapsack and the other approaches, on a scale where each line up is 10 times more steps.
  • Unbounded knapsack, Breadth-first search over totals O(amount × coins)
  • Greedy, biggest coin first O(n log n)
  • Plain recursion O(2^n)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Unbounded knapsack1001 million1 trillion
Greedy, biggest coin first339,96620 million
Breadth-first search over totals1001 million1 trillion
Plain recursion1,024more than a quadrillionmore than a quadrillion

Inputs that need care

5 tricky inputs
amount = 0
The loop never runs and it returns fewest[0], which is 0. No coins are needed.
An impossible amount: coins = [2, 4], amount = 3
fewest[3] stays Infinity, so line 11 returns -1. Every odd total is impossible with even coins.
A coin bigger than the amount
coin <= total is never true for it, so it is never used. No special check is needed.
Duplicate coins: coins = [5, 5, 2]
The answer is the same; the second 5 just repeats the same option. Remove duplicates first if the coin list is long.
A coin worth 0
Here it is harmless, because fewest[total] + 1 is never smaller than fewest[total]. In the counting version it would be added again and again, so reject zero coins.

Variations and follow-ups

Twists interviewers add

Counting combinations versus orders

To count the ways to make the amount, store counts and add instead of taking the minimum. With coins in the outer loop and totals inside, each mix is counted once: 3 ways to make 10 from 2, 5, and 6. With totals outside and coins inside, each order counts separately: 5 ways.

Most value in a bag, with unlimited copies

The original knapsack form gives each item a weight and a value. best[cap] is the most value that fits in cap, and it reads best[cap - weight] + value for every item. Cutting a rod into priced lengths is this problem.

Fewest squares

To write a number as a sum of the fewest perfect squares, the coins are 1, 4, 9, 16, and so on, up to the number. The table and the loops are the same.

Breadth-first search view

You can also see totals as nodes and coins as edges from total to total + coin. A breadth-first search from 0 finds the fewest coins as the fewest edges, and it can stop as soon as it reaches amount.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from "unlimited supply", "each item can be used any number of times", or "fewest pieces to make a total". If items can be used once each, it is the 0/1 knapsack instead.
  • Say why greedy fails with a concrete counterexample, like 10 from coins 2, 5, and 6. It shows you checked, and it explains why you need a table.
  • Explain the Infinity start: it means "not possible yet", and Infinity + 1 stays Infinity, so impossible amounts never win. Then show fewest[0] = 0 as the only base case.
  • Expect "now count the ways instead". Change Math.min to a sum, set ways[0] = 1, and ask whether order matters, because that decides which loop goes outside.

Where frontend code uses it

The same idea in real UI code
  • Checkout code that combines reusable coupon types or gift card denominations to reach an exact discount is this table.
  • Filling a row of a fixed width with tiles or cards that come in a few standard widths, such as a 12-column grid with 2, 3, and 4 column cards, is the counting version.
  • Cutting a long timeline into standard-length clips to get the most value is the "rod cutting" version.

Related algorithms