Knapsack and coin change

Why it matters

These problems are the template for a whole family of DP questions. Each one asks you to choose items under a limit, count the ways to reach a total, or find the smallest or largest total that fits. If you understand knapsack and coin change, then subset sum, partition, target-sum and many "can we make this amount" questions follow with small changes. Interviewers use them because they test the recurrence, the base cases, and the loop order all at once.

This lesson has four parts. Each part adds one idea. The first is the 0/1 knapsack, where each item can be taken once or not at all. The second is coin change, where you minimise the number of coins and each coin can be reused. The third counts the ways to make an amount, and it shows how a small change in loop order changes the meaning of the answer. The fourth is subset sum, which asks a yes or no question. Each part uses a one-dimensional table and the same five-step recipe from the last lesson.

Part 1: the 0/1 knapsack

Imagine a hiker with a backpack that can carry at most 7 kilograms. There are several items. Each item has a weight and a value, which is how much the hiker wants it. Each item is either packed whole or left behind. You cannot take half of a tent. The goal is to pack the bag so the total value is as large as possible without going over the weight limit. This is the 0/1 knapsack problem. The name comes from the choice for each item: 0 for leave it, 1 for take it.

Why greedy fails

A tempting idea is to sort the items by value per kilogram and take them in that order until the bag is full. This is called a greedy method, because it makes the locally best choice at each step and never looks back. For many problems greedy works, but not for the knapsack.

Here is a counterexample. The bag holds 50 kilograms. There are three items: item A weighs 10 kg and is worth 60, item B weighs 20 kg and is worth 100, and item C weighs 30 kg and is worth 120. Per kilogram, A is worth 6, B is worth 5, and C is worth 4. Greedy takes A first, then B, which uses 30 kg, and then it cannot fit C, because 30 kg more would make 60 kg. The greedy total is 60 + 100 = 160.

The best choice is B and C together. They weigh 20 + 30 = 50 kg exactly, and they are worth 100 + 120 = 220. Greedy's first choice, the item with the best ratio, blocked the best pair. A choice that looks best now can be wrong later, and DP is the tool that compares the whole set of options.

Defining the table

Let dp[c] mean "the best value that fits in a bag of capacity c, using only the items seen so far". Capacity here means the largest total weight the bag can hold, so dp[c] allows any total weight up to c. At the start, with no items, every capacity has value 0.

Now take one item with weight w and value v. For each capacity c, there are two options. Leave the item: the value stays dp[c]. Take the item: the bag must have room for w, so the rest of the bag has capacity c - w, and the value is dp[c - w] + v. Take whichever is larger:

dp[c] = max(dp[c], dp[c - w] + v)

This recurrence is only valid when c is at least w. For smaller capacities the item simply does not fit, and the value stays the same.

The loop must run downwards

The most important detail is the loop direction. The capacity c must run from the largest value down to w. Here is why. The right-hand side reads dp[c - w]. That cell must still hold the value from before this item was considered. If the loop went upwards, dp[c - w] would already have been updated for this item, and the item would be counted again. The item would be used once for dp[c - w] and again for dp[c], so the same item is used many times. That is the unlimited version of the problem, and it is a different question.

Take a small example to see the difference. There is one item with weight 1 and value 1, and the bag capacity is 3. The correct answer is 1, because the item can be taken only once. Go downwards and you get 1. Go upwards and you get 3, because the program takes the same item three times.

Here is the downward pass for capacity 3 with that one item. Start with dp equal to 0 0 0 0 for capacities 0 to 3. The loop visits c = 3, then 2, then 1. At c = 3, dp[3] = max(0, dp[2] + 1) = max(0, 0 + 1) = 1. At c = 2, dp[2] = max(0, dp[1] + 1) = 1. At c = 1, dp[1] = max(0, dp[0] + 1) = 1. The result is 0 1 1 1. Each step read an old value, because the cells it read had not been changed yet.

A worked trace with a table

Now take the four items from the diagram: weights and values of (1, 1), (3, 4), (4, 5) and (5, 7), with capacity 7. Each row below shows the dp values for capacities 0 to 7 after one more item has been processed. The first row has no items.

Knapsack table with one row per item and one column per capacity from 0 to 7, the last cell highlighted as 9

Read the table row by row. After item (1, 1), each capacity from 1 up can hold that item, so the values are 0, 1, 1, 1, 1, 1, 1, 1. After item (3, 4), capacity 3 becomes 4, and capacity 4 becomes 5, because the bag can hold both the 1 kg item and the 3 kg item. Going down through the capacities keeps each item from being used twice.

The last row is the answer. The value at capacity 7 is 9. That comes from taking items 3 and 4, which weigh 3 + 4 = 7 and are worth 4 + 5 = 9. The table did not need to know which items those were. It only needed the values, and the recurrence gave the best one.

The Viz below walks through the same table one cell at a time. Watch how each new row reads the row above it, and notice that every write happens after the read that needs the old value.

The program

Here is the complete 0/1 knapsack program. It reads the number of items and the capacity, then one line per item with its weight and value.

Type 4 7 in the Input box, press Enter, then type the four item lines 1 1, 3 4, 4 5 and 5 7 on separate lines, and press Run.

Output:

best value = 9

The program uses two vectors for the input data and one for the table. The table has cap + 1 cells, so the space is O(cap). Each item loops over at most cap cells, so the time is O(n times cap), where n is the number of items. This is called pseudo-polynomial time, and it deserves a precise explanation. The time depends on the size of the number cap, not only on how many items there are. A capacity of a million with 100 items is 100 million steps, which is fine in C++, but a capacity of 10 to the 18th would be impossible. The problem's limits decide whether this method is good enough.

Rebuilding the chosen items

The program prints the best value, but a real user usually wants the list of items. The one-row table cannot give that back, because it overwrote the old rows as it went. To recover the choices, keep the whole table, with one row for each prefix of the items. Row i holds the best values when only the first i items are allowed.

Now the answer is at the bottom right, dp[n][cap]. Walk back from there. If dp[i][c] equals dp[i - 1][c], the value did not depend on item i, so it was left out. If the values differ, item i was taken, and the bag had c - w[i] room left for the earlier items. Jump to that cell and carry on.

The program below does the rebuild. It uses the same input as the first knapsack program, so you can compare the two.

Type 4 7 in the Input box, press Enter, then type 1 1, 3 4, 4 5 and 5 7 on separate lines, and press Run.

Output:

best value = 9
chosen items: 3 2

The list comes out from the last item to the first, so 3 2 means items 2 and 3 were packed. The two items weigh 3 + 4 = 7 kg and are worth 4 + 5 = 9. The table is O(n times cap) in space, which is more than the one-row version needs, so use it only when the choices are part of the answer. When the question asks for the value alone, the one-row version is the better choice.

Part 2: coin change, the fewest coins

Now a different question. You need to pay an exact amount using coins of given values. You have unlimited coins of each value. The goal is the fewest coins that add up to the amount, or -1 if no combination works. This is coin change.

The table has a different meaning. Let dp[a] be the fewest coins that add up to exactly a. The base case is dp[0] = 0, because zero coins make zero. For every other amount, try each coin c that is not larger than a. If you use coin c as the last coin, the rest of the amount is a - c, and you need dp[a - c] coins for that part. So the candidate is dp[a - c] + 1. Take the smallest candidate:

dp[a] = min(dp[a], dp[a - c] + 1)

Before you fill the table, every cell except dp[0] must hold a large marker meaning "not yet known, or impossible". The usual choice is a big number such as 1,000,000,000. If an amount truly cannot be made, the cell keeps that marker, and the program reports -1. The marker must never be 0, because min would then keep 0 and claim the amount needs no coins at all. That bug is covered in the mistakes section.

A worked trace

Take coins 1, 3 and 4, and the amount 6. A greedy method would take the biggest coin first: 4, then 1, then 1, which is three coins. The DP table finds a better answer. Here is the table for amounts 0 to 6, with the marker written as inf.

Walk through two cells. For amount 2, the only useful coin is 1, which leaves amount 1, and dp[1] = 1, so dp[2] = 2. For amount 6, try each coin. Coin 1 leaves amount 5, which needs 2 coins, so the candidate is 3. Coin 3 leaves amount 3, which needs 1 coin, so the candidate is 2. Coin 4 leaves amount 2, which needs 2 coins, so the candidate is 3. The minimum is 2, from 3 + 3. Greedy missed it, and DP found it without any special rule.

The Viz below steps through the coin change table cell by cell. Watch which earlier cells each new cell reads. The reads always point to smaller amounts.

The program

Here is the complete coin change program. The first line of input holds the amount and the number of coins. The second line holds the coin values.

Type 11 3 in the Input box, press Enter, type 1 2 5 and press Run.

Output:

fewest coins = 3

The check dp[a - c] != INF is important. If the smaller amount is impossible, its value is the marker, and adding 1 to the marker would produce a number just above the marker. That number might look like a real answer in some cases, and with INT_MAX as the marker the addition would overflow. Skipping impossible smaller amounts avoids both problems.

Change the input to 3 1 followed by 2, which asks for amount 3 with only a coin of value 2. The program prints fewest coins = -1, because 3 is odd and no combination of 2s makes it. A correct program must report impossibility. Many beginner solutions print the marker instead, and a marker like a billion looks like a valid answer to a reader.

Complexity. The loop does one step for each pair of amount and coin. That is O(amount times k) time, where k is the number of coin values, and O(amount) space for the table.

Part 3: counting the ways

The third problem asks a related question. How many different ways are there to make the amount? Now the answer is a count, not a minimum, and the order of the coins matters for the code.

There are two different questions hidden in "how many ways". The first asks for combinations: two ways are the same if they use the same coins, whatever order they appear in. The second asks for orders: 1 + 2 and 2 + 1 count as different ways. The two need different loop orders. This is one of the most useful things to learn in this module, because interviewers sometimes ask about the difference, and it is easy to get wrong.

For combinations, put the coins in the outer loop and the amounts in the inner loop. Each coin type is processed once, and the amounts that use it are added on top of the amounts that do not. The counts never mix an order.

For orders, put the amounts in the outer loop and the coins in the inner loop. Each amount is built from every coin, so a sequence that ends with a 2 is counted separately from one that ends with a 1.

Take amount 3 and coins 1 and 2. The combinations are 1 + 1 + 1 and 1 + 2, which makes 2. The orders are 1 + 1 + 1, 1 + 2 and 2 + 1, which makes 3. The program below computes both, so you can see the difference in one run. It reads the amount and number of coins, then the coin values.

Type 3 2 in the Input box, press Enter, type 1 2 and press Run.

Output:

combinations = 2
orders = 3

Study the first loop. Coin 1 is processed first. It makes every amount reachable as a sum of 1s, so after that loop combos holds 1 for amounts 0 to 3. Coin 2 is processed next. For amount 2 it adds combos[0], which records the way 2 alone. For amount 3 it adds combos[1], which records the way 1 + 2. The result is 2.

Now study the second loop. For amount 3, the code adds orders[2] for a coin of 1 and orders[1] for a coin of 2. The value orders[2] already counts 1 + 1 and 2, so adding a 1 at the end gives 1 + 1 + 1 and 2 + 1. The value orders[1] counts 1, so adding a 2 gives 1 + 2. That is three ways in total.

Both loops read only smaller amounts, so the table order is always safe. The only difference is where the coin loop sits. This small change turns a count of coin sets into a count of sequences, and that is exactly the kind of detail an interviewer checks.

Why long long? Counting ways grows very fast. Even for modest inputs, the number of sequences can exceed the range of a 32-bit int. Use long long for counts, and check whether the problem asks for a modulus, such as "give the answer modulo 1000000007". If it does, reduce each addition modulo that number, so the values never grow past the type's limit.

Part 4: subset sum

The last problem in this lesson asks a yes or no question. Given a list of numbers and a target, can some of the numbers add exactly to the target? This is subset sum. Each number is used at most once, so the table is like the 0/1 knapsack, but the values are true or false, not numbers.

Let can[s] mean "some subset of the numbers seen so far adds exactly to s". The base case is can[0] = true, because the empty subset adds to zero. For each number x, the new value for sum s is true if the old value was true (leave x out) or if can[s - x] was true (use x). That gives the recurrence:

can[s] = can[s] || can[s - x]

The loop must run downwards for the same reason as the knapsack. Going down means can[s - x] still holds the answer before x was considered, so x is used at most once. Going up would allow the same number to be reused, and the answer would be wrong for targets that need a single copy of a number.

The program below reads a count and a target, then the numbers. It answers YES or NO.

Type 5 9 in the Input box, press Enter, type 3 34 4 12 5 and press Run.

Output:

can make 9: YES

The subset that works is 4 and 5. The number 34 is larger than the target and is skipped automatically, because the loop for that number never runs: s starts at the target and stops before reaching 34.

The Viz below steps through the same kind of table. Its cells are numbers, not booleans, but the reads and writes follow the same pattern as the earlier tables, so use it to check your understanding of the loop direction.

Subset sum is the basis of several well-known interview questions. Partition asks whether an array can be split into two groups with equal sums. That is subset sum with the target equal to half the total, when the total is even. Target sum asks how many ways to add plus and minus signs to the numbers give a target value, which counts subsets with a certain sum. Each of these is a small change to the table above.

What happens inside

It helps to see the memory use of these tables. A vector<int> of cap + 1 entries holds 4 * (cap + 1) bytes on a typical system, because an int takes four bytes. A capacity of 1,000 uses about 4 kilobytes. The table is one contiguous block, and the loops walk through it in order, so the processor reads and writes memory predictably. That is one reason the table version is fast in practice.

The vector<bool> used by subset sum is a special case. C++ stores each bool as a single bit, not a full byte, so a table of a million flags uses about 125 kilobytes. That makes it a good choice for large yes or no tables, although bit-level access is a little slower than byte access.

The work per cell is one comparison, one addition and one store. For the knapsack that means the total work is the number of items times the capacity. For coin change it is the amount times the number of coins. Multiply the sizes of the two inputs to estimate the running time. A quick estimate like this often tells you whether a method is fast enough before you write it.

Common mistakes

Looping capacity upwards in 0/1 knapsack. The program still runs, and it prints a number. The number is the answer to the unlimited version, where an item can be taken many times. Check the loop direction whenever the item may be used at most once.

Using INT_MAX as the marker, then adding 1. A beginner writes vector<int> dp(amount + 1, INT_MAX) and later computes dp[a - c] + 1 without checking. If dp[a - c] is INT_MAX, the addition overflows. In C++ that is undefined behaviour, and in practice the sum wraps to a large negative number that min then chooses. The safe choice is a smaller marker, such as one billion, together with a check that the smaller amount is reachable.

If you forget the include, the compiler stops you before the program runs. Here is what g++ prints for a program that uses INT_MAX without #include <climits>:

im.cpp: In function ‘int main()’:
im.cpp:5:13: error: ‘INT_MAX’ was not declared in this scope
    5 |     cout << INT_MAX << "\n";
      |             ^~~~~~~
im.cpp:2:1: note: ‘INT_MAX’ is defined in header ‘<climits>’; this is probably fixable by adding ‘#include <climits>’

The error names the missing word, and the note line tells you the header that defines it. The fix is the include, #include <climits>, at the top of the file.

The same lesson applies to every standard name. A name that the compiler does not recognise usually means a missing #include, a missing using namespace std;, or a typo.

How the four problems fit together

The four problems in this lesson look different, but they share one table shape and one question: what does each cell mean? The table below puts them side by side, so you can see what changes from one to the next.

Two columns carry most of the lesson. The base case tells you what the empty input is worth, and the loop direction tells you whether an item can be reused. When you meet a new problem, fill in the first two columns before anything else. If you cannot, the problem is not yet understood, and no amount of code will fix it.

What happens inside

It helps to see the memory use of these tables.

Forgetting to return -1. When the amount is impossible, the table still holds the marker. If the function returns the marker, the output is a huge number. Check the marker before you return.

Filling the coin table with zero. If every cell starts at 0, then min keeps 0 everywhere, and every amount claims to need zero coins. This is the bug in the spot-the-bug question of the quiz. Only dp[0] should be zero.

Counting combinations with the amount loop outside. The result is the number of sequences, not the number of sets. The fix is to swap the loops, but only if the question asks for sets. Read the question carefully.

Overflow in counting. Counts of ways grow fast. A long long holds values up to about 9 times 10 to the 18th. Past that, use a modulus, or a bigger type if your language offers one.

Debugging walkthrough

Suppose the coin change program prints 4 for amount 6 with coins 1, 3 and 4, and you expected 2. The steps you would take are the same as in the last lesson, but the details differ.

First, print the table. Add a line after the loop that prints every dp[a] for a from 0 to 6. You should see 0, 1, 2, 1, 1, 2, 2. If the printed values are different, look at the first cell that is wrong.

Second, check the first wrong cell by hand. Suppose dp[3] prints 3, not 1. The cell for amount 3 should see the coin 3 and set the value to dp[0] + 1 = 1. If the program did not see coin 3, check the loop over the coins, and make sure the condition c <= a is written correctly.

Third, check the marker logic. If a cell is the marker, the code must not add 1 to it. Print the marker and make sure the check dp[a - c] != INF is there.

Fourth, test the edge cases below. Each one isolates one part of the logic.

Variations and edge cases

Test these inputs before you trust a solution.

• Amount 0. The answer is 0 coins, and the table has one cell.
• An amount that is one coin exactly. The answer is 1.
• An amount that cannot be made, such as 3 with only the coin 2. The answer is -1.
• A coin larger than the amount. The condition c <= a skips it, and the program must not read a negative index.
• Zero items or zero coins. The knapsack answer is 0, and the coin answer is -1 for any positive amount.
• An item heavier than the capacity. It is never taken, and the loop for that item does nothing.
• Duplicate coin values. For minimum coins they change nothing. For counting combinations, they make a different question, so check whether the coins are required to be distinct.

For knapsack, the variations change the rule for each item. If each item has unlimited copies, loop upwards, and the program becomes the unlimited knapsack. If items have a count limit, the recurrence adds a loop over the copies. If you need the actual set of items, keep the full table of rows and walk back from the answer, the same way you rebuilt the choices in the last lesson.

Interview questions

These are typical questions about this lesson's problems, with short model answers.

"Why does greedy fail for the 0/1 knapsack?" Answer: the item with the best ratio can block a better pair of items. Give the counterexample: capacity 50 with items worth 60, 100 and 120 at weights 10, 20 and 30. Greedy gives 160. The best is 220.

"Why does the knapsack loop go downwards?" Answer: the update reads the old value of a smaller capacity. Going downwards makes sure that value is still from before this item was added, so each item is used at most once.

"How do you count the ways to make an amount, if order does not matter?" Answer: put the coins in the outer loop and the amounts in the inner loop. Explain that each coin is processed once, so the counts are sets.

"What is the time complexity of coin change?" Answer: O(amount times k), where k is the number of coins, and O(amount) space. Say that the time depends on the size of the amount, which makes it pseudo-polynomial.

"How would you check whether a number can be split into two equal halves?" Answer: compute the total. If it is odd, the answer is no. Otherwise run subset sum for half the total. This is the partition problem.

Practice

1. Easy. Run the knapsack with capacity 10 and items (weight 5, value 10), (weight 4, value 40), (weight 6, value 30) and (weight 3, value 50). Predict the answer before you check it. Hint: find the pair of items that fits and has the highest value.

2. Easy. Coin change with coins 2 and amount 3 returns -1. Explain in one sentence why the table cell for amount 3 keeps the marker.

3. Easy. Explain why dp[0] is 0 for coin change, but the other cells start at the marker.

4. Medium. Make the table for coins 1, 3 and 4 and amount 8. Find the fewest coins without the program. Then check with the program.

5. Medium. Count the combinations for amount 5 and coins 1, 2 and 5. Predict the answer, which is 4, and list the four combinations.

6. Medium. Explain what the knapsack program would print if the inner loop went upwards, using one item of weight 1 and value 1 with capacity 3.

7. Medium. Change the subset sum program so that it prints the number of subsets that add to the target, not just yes or no. The vector<bool> becomes a count, and you must think about the initial value.

8. Medium. A teammate's coin change code starts every cell at 0 and prints 0 for amount 6 with coins 1, 3 and 4. Explain the bug and show the fix.

9. Hard. Partition: given 1 5 11 5, decide whether the numbers can be split into two groups with equal sums. Reduce it to subset sum and give the target.

10. Hard. Target sum: given five 1s and a target of 3, count the ways to put a plus or minus sign in front of each number so that the signed sum is 3. Reduce it to counting subsets with a fixed sum, and give the answer.

What you now know

• The 0/1 knapsack keeps one best-value row, and each item's loop must run downwards.
• Greedy choices by value per weight can miss the best pair of items.
• Coin change minimises the number of coins, and the table must start with a marker that is never zero except at the base case.
• The number of ways depends on the loop order: coins outside gives sets, amounts outside gives sequences.
• Subset sum uses a table of true or false values, with the same downwards loop as the knapsack.
• Pseudo-polynomial time means the running time depends on the size of a number in the input, not only on the number of items.
• The next lesson moves to two dimensions, with grid paths, longest common subsequence and longest increasing subsequence.