Unbounded knapsack and rod cutting in Python

Why this matters

A knapsack problem asks how to fill a limited space with the most valuable things. A shop that cuts steel bars into pieces, a truck that loads boxes, and an online store that picks items for a fixed budget all face this kind of problem. Often there are many copies of the same kind of thing, so you may take more than one.

The knapsack lesson earlier in this module covered the case where each item exists only once. This lesson covers the case where you can take as many copies as you like. The code change is small: the direction of one loop. The reason behind that change is the main idea to learn.

By the end you will be able to say what "unbounded" means, fill a table by hand for a small case, write the Python loop, see what goes wrong when the loop runs the wrong way, and solve rod cutting as a knapsack problem.

Reading the code in this lesson

The code uses a few Python features. You need only these to follow it.

• A list such as [2, 3, 4] is an ordered row of values. Each value has a number called an index. The first value has index 0.
• best[i] reads or writes the value at index i.
• len(best) is the number of values in the list.
• [0] * 8 makes a list of eight zeros.
• range(1, 8) gives the numbers 1 to 7. The end number is not included, so range(1, capacity + 1) goes up to capacity.
• zip(weights, values) pairs up two lists. In a loop, weight, value takes one pair at a time.
• max(a, b) returns the larger of two numbers.
• price[1:] is a slice. It makes a new list from index 1 to the end.
• An f-string such as f"answer = {best[7]}" puts the value of the expression inside the braces into the text.
• Type hints such as list[int] are notes for readers. Python does not check them when the program runs.

Readers who know Java: Python has no type declarations on variables, and a Python list is closer to a Java ArrayList than to an array.

The problem in plain words

Picture a bag that holds at most 7 kilograms. The capacity of the bag is 7. Three kinds of item are on the table. Each kind has a weight, the kilograms it adds to the bag, and a value, the points you get for taking one.

• Item A: weight 2, value 3
• Item B: weight 3, value 4
• Item C: weight 4, value 5

You may take as many copies of each kind as you want. The goal is the largest total value with total weight at most 7. This version is called unbounded because no item has a limit on copies. In the 0/1 version, each item exists once, so you either take it or leave it.

Try a few bags by hand:

• One C and one B: weight 4 + 3 = 7, value 5 + 4 = 9.
• Two A and one B: weight 2 + 2 + 3 = 7, value 3 + 3 + 4 = 10.
• Three A: weight 6, value 9.
• Two B: weight 6, value 8.

The best of these is 10, from two A and one B. A brute-force search tries every combination of items. That works for a handful of items, but the number of combinations grows quickly as the capacity grows. The rest of the lesson builds a faster method.

Build the answer from smaller answers

The method fills a table with one entry for each capacity. Let best[w] be the largest value that fits in a bag of capacity w. The table has entries for capacities 0 through 7, so it has eight slots.

Start with best[0] = 0. A bag of capacity zero holds nothing, so its best value is zero.

For a bigger capacity w, pick one item to put in the bag. Suppose we pick A, which weighs 2. The bag then has w - 2 kilograms of room left, and the best we can do with that room is best[w - 2]. So taking A gives best[w - 2] + 3 in total. Do the same for B and C, then keep the largest result. This gives the rule:

best[w] = largest of (best[w - weight] + value), over every item that fits

A rule that builds each answer from earlier answers is called a recurrence. Here, the answer for capacity 7 is built from the answers for capacities 5, 4 and 3, because those are the bags left over after taking A, B or C.

Fill in the table by hand:

• best[1]: no item weighs 1, so nothing fits. The value is 0.
• best[2]: A fits. best[0] + 3 = 3. The value is 3.
• best[3]: A gives best[1] + 3 = 3. B gives best[0] + 4 = 4. The largest is 4.
• best[4]: A gives best[2] + 3 = 6. B gives best[1] + 4 = 4. C gives best[0] + 5 = 5. The largest is 6.
• best[5]: A gives best[3] + 3 = 7. B gives best[2] + 4 = 7. C gives best[1] + 5 = 5. The largest is 7.
• best[6]: A gives best[4] + 3 = 9. B gives best[3] + 4 = 8. C gives best[2] + 5 = 8. The largest is 9.
• best[7]: A gives best[5] + 3 = 10. B gives best[4] + 4 = 10. C gives best[3] + 5 = 9. The largest is 10.

The table of results, with one way to fill each bag:

Look at the row for capacity 4. Its value 6 uses A twice. The entry best[4] reads best[2], and best[2] already holds the value of a bag with one A in it. Adding one more A is allowed, because nothing says an item can be used only once. That is the whole idea behind "unbounded".

Loop upward so that items can be reused

The Python code follows the table. The outer loop moves the capacity w upward from 1 to 7. The inner loop tries each item.

Save the file as knapsack.py and run it with python3 knapsack.py. The output is:

best[0..7] = [0, 0, 3, 4, 6, 7, 9, 10]
answer for capacity 7 = 10

The list printed is the table from the previous section, read from index 0 to index 7.

Here is what each part does:

• [0] * (capacity + 1) makes the table with one slot for each capacity from 0 to 7. The + 1 is needed because the last slot is at index 7.
• The outer loop goes up: w is 1, then 2, then 3, and so on.
• The check weight <= w skips an item that is too heavy for the bag.
• best[w - weight] reads the entry for the room left after taking the item. That entry is smaller than w, so the outer loop has already finished it.
• Because the entry read may already include the item, taking the item again is allowed.

The direction of the outer loop is the key choice. Going up means each smaller capacity is complete before a larger one reads it. Going down would make the loop read entries that are not finished yet, and each item would then be counted only once. The mistakes section shows that case.

Walking through one entry in detail

To see the reuse step by step, look at w = 6 in the table. The loop tries the items in order A, B, C.

When the loop reaches A, it reads best[4], which the outer loop already finished as 6. So the candidate is 6 + 3 = 9. The entry best[4] already means "a bag of capacity 4 holds two As", so the candidate means "three As".

When the loop reaches B, it reads best[3], which is 4 and means one B. The candidate is 4 + 4 = 8, which is two Bs, weight 6.

When the loop reaches C, it reads best[2], which is 3 and means one A. The candidate is 3 + 5 = 8, which is one A and one C, weight 6.

The largest candidate is 9, so best[6] = 9. The walk shows that every candidate is built from an earlier entry, which is already final. This is why the table can be filled in one pass.

Rod cutting: the same loop

A rod is a long piece of metal or wood. A buyer pays a price for each piece of a given length. You may cut the rod into pieces, or sell it whole. The goal is to get the most money.

Use this price list. A piece of length 1 sells for 1. A piece of length 2 sells for 5. A piece of length 3 sells for 8. A piece of length 4 sells for 9. A piece of length 5 sells for 10. A piece of length 6 sells for 17. A piece of length 7 sells for 17. A piece of length 8 sells for 20.

Here are some ways to cut a rod of length 8:

• Keep it whole: 20.
• Cut it into lengths 2 and 6: 5 + 17 = 22.
• Cut it into lengths 3 and 5: 8 + 10 = 18.
• Cut it into lengths 1 and 7: 1 + 17 = 18.
• Cut it into four pieces of length 2: 5 + 5 + 5 + 5 = 20.

The best of these is 22, from a piece of length 2 and a piece of length 6.

The rule has the same shape as the knapsack rule. Let best[length] be the best total for a rod of length length. Choose one piece to cut off first. Call its length cut. It sells for price[cut], and the rest of the rod has length length - cut. So:

best[length] = largest of (price[cut] + best[length - cut]), for cut from 1 to length

Put the two problems side by side. The rod is the bag. The length of a piece is its weight. The price of a piece is its value. Reusing a length is allowed, because a rod can have two pieces of the same length. So the same loop works.

Here is the Python code for the rod. It also runs the knapsack function on the same prices, as a check that the two problems give the same table.

Save the file as rod_cutting.py and run it with python3 rod_cutting.py. The first two lines are the knapsack result from before. The output is:

best[0..7] = [0, 0, 3, 4, 6, 7, 9, 10]
answer for capacity 7 = 10
best[0..8] = [0, 1, 5, 8, 10, 13, 17, 18, 22]
best price for rod of length 8 = 22
via knapsack          = [0, 1, 5, 8, 10, 13, 17, 18, 22]

Both tables match, and the answer for length 8 is 22, the value found by hand.

The price list has a dummy value at index 0, so that price[length] is the price of a piece of that length. The slice price[1:] takes the prices for lengths 1 to 8, so fill_table receives weights and values that line up.

Example two: the largest value first is not always right

A tempting shortcut is to take the most valuable item first and keep going. Test that idea on a small case. The bag has capacity 6. Item A weighs 4 and is worth 9. Item B weighs 3 and is worth 6.

Taking A first gives value 9. That leaves 2 kilograms of room, which is too small for B. The total is 9.

Taking B twice fills the bag exactly, with weight 6 and value 12. So the best answer is 12, and the shortcut missed it.

The table handles this case without a special rule. This uses the fill_table function from the knapsack section:

best = fill_table([4, 3], [9, 6], 6)
print(best[6])

The output is 12. The entry best[6] tries A and gets best[2] + 9 = 9. It also tries B and gets best[3] + 6. The entry best[3] is 6, from one B, so the candidate is 12. The table compares both choices at every step, so it does not need to guess which item is best.

Example three: the fewest coins

The same loop works when the goal is a minimum. A cashier wants to pay an amount using as few coins as possible. The coin values are 1, 2 and 5. The amount is 11.

The answer is 3 coins: 5, 5 and 1. Here is the Python code.

The output is:

coins [1, 2, 5], amount 11: 3
coins [2], amount 3: -1

This version has two changes from the knapsack code.

First, min replaces max, because we want the fewest coins.

Second, the table starts with math.inf (infinity) in every entry except fewest[0]. A sentinel is a value chosen to mean "special" rather than a real count. Here math.inf means "no way found yet". It is a float, which is a number that can hold a decimal part. Adding 1 to infinity still gives infinity, so the code can add a coin without checking first. The last if turns infinity into the signal -1, which means "impossible". The second line of output is -1 because 3 cannot be made from coins that are all 2.

Python integers have no fixed size. A Python number grows as large as the computer's memory allows, so a sum never wraps around to a negative number. Run this:

The output is:

2147483648
1267650600228229401496703205376
1267650600228229401496703205377

The first line is one more than 2147483647, the largest whole number that fits in a signed 32-bit integer. Many languages store whole numbers in a fixed size like this, and a sum past the limit wraps around. Python does not have that limit, so this program needs no special check for overflow.

Common mistakes

Looping the capacity downward

The most common mistake is to count the capacity downward, from the largest value to 1. The code still runs and prints a number, but the number is wrong for this problem. This program has the wrong loop and the right loop, one after the other, so you can compare them:

The output is:

downward loop: [0, 0, 3, 3, 3, 3, 3]
upward loop:   [0, 0, 3, 3, 6, 6, 9]

Here is why the downward loop gives 3 at capacity 6. The item weighs 2 and is worth 3. When w is 6, the loop reads best[4]. But the downward loop has not yet set best[4], so it is still 0. The candidate is 3. The same thing happens at every capacity, so every entry gets one copy and nothing more. The result is the 0/1 answer, which is 3, not the unbounded answer, which is 9 (three copies of the item).

The fix is to loop upward, as in the knapsack code.

Forgetting the weight check

If the check weight <= w is missing, Python does not stop with an error. It reads the wrong entries and gives a wrong answer. A negative index counts from the end of the list. So when w - weight is -1, Python reads the last entry, not a missing one.

The code below is the knapsack loop without that check, using the same weights as the main example:

The output is:

[0, 5, 5, 8, 9, 11, 12, 14]

The entry at index 1 is 5, but nothing fits in a bag of capacity 1, so the correct value is 0. When w is 1 and an item weighs 2, w - weight is -1. Python reads the last entry, best[7], which is still 0 at that point. The other items read best[6] and best[5], which are also still 0. The largest candidate is 5 from the weight-4 item, so best[1] becomes 5. Later entries read these wrong values, so the error spreads. The last entry prints 14, but the correct answer for capacity 7 is 10.

A negative index only raises an error when it is less than minus the length of the list. For a list of 8 entries, best[-8] is the first entry, and best[-9] raises IndexError: list index out of range. So a missing check does not crash here, which makes it harder to find. The fix is the if weight <= w check, which skips items that are too heavy.

Practice

Exercise 1. Items: weight 3 worth 4, weight 4 worth 5, weight 5 worth 7. The bag holds 10 kilograms, and you may take any number of copies. What is the best value?

Show the answer

The answer is 14. Two copies of the weight-5 item weigh 10 and are worth 14. The other full combination, 3 + 3 + 4, is worth only 13. Running fill_table with these inputs prints 14 for capacity 10.

Exercise 2. A rod of length 6 sells as follows: length 1 for 1, length 2 for 5, length 3 for 8, length 4 for 9, length 5 for 10, length 6 for 17. What is the best total for a rod of length 6?

Show the answer

The answer is 17, from keeping the rod whole. Two pieces of length 3 give 16, and three pieces of length 2 give 15. Running rod_table with these prices gives 17 for length 6.

Exercise 3. Use the rod prices from exercise 2 but change the rule: pieces may be at most length 3. What is the best total for a rod of length 8?

Show the answer

The answer is 21, from pieces of lengths 3, 3 and 2, worth 8 + 8 + 5. Running fill_table with lengths 1 to 3 and prices 1, 5 and 8 gives 21 for capacity 8.

Exercise 4. Run the downward loop from the mistakes section with one item that weighs 1 and is worth 2, and capacity 4. What number does it print?

Show the answer

It prints 2. When w is 4, the loop reads best[3], which is still 0 because the downward loop has not reached 3 yet. The candidate is 2, and every other capacity gets the same result. So the answer is 2, not the unbounded answer 8.

Exercise 5. Find the fewest coins that make 11 when the coins are 1, 2 and 5. Then find the answer for an amount of 3 when the only coin is 2.

Show the answer

For 11, the answer is 3 coins: 5, 5 and 1. For 3 with only 2-coins, the answer is -1, because an odd amount cannot be made from 2s alone. The fewest_coins function prints these values.

Summary

• An unbounded knapsack lets you take any number of copies of each item.
• The table entry best[w] is built from best[w - weight], so loop the capacity upward so that entry is already final.
• Looping downward allows only one copy of each item and gives the wrong answer.
• Rod cutting is the knapsack with piece lengths as weights and piece prices as values.
• For a minimum, use min, and start unreachable entries with math.inf, which stays infinite when 1 is added.
• Rebuilding which pieces to cut needs stored choices, which the later lesson on storing choices covers.