Unbounded knapsack and rod cutting

Why this matters

The knapsack lesson covered the case where each item can be packed once or not at all. Many real questions are different. A shop sells a product in unlimited quantity, a cutting machine can make the same size piece again and again, and a timer can run the same task many times. The question then becomes: how do you fill a limit with copies of the items you have, and get the best total?

This lesson has three parts. The first changes one detail of the 0/1 knapsack so that an item can be reused. The second shows a table of results for a small example, so you can see how the reuse shows up cell by cell. The third applies the same method to a different problem, cutting a rod into pieces to earn the most money. The rod problem is a classic interview question, and it is the same table as the knapsack once you see which number plays which role.

You should already know the table idea from the knapsack and coin change lesson, where dp[c] means the best value that fits in capacity c. This lesson uses that meaning and changes only the loop.

Part 1: reusing an item

Start with a small question. A hiker has a bag that holds 7 kilograms. A shop sells one kind of bag of food. Each bag weighs 3 kg and is worth 4 points to the hiker. The shop has as many bags as the hiker wants. How many bags should the hiker take?

Two bags weigh 6 kg and are worth 8 points. Three bags would weigh 9 kg, which is over the limit. So the answer is 8, and the hiker takes two bags with 1 kg free.

If the hiker could take only one bag, the answer would be 4. That is the 0/1 version, which the knapsack lesson handled. The difference is one line in the code, but it changes the answer.

The difference from the 0/1 version

In the 0/1 version the capacity loop runs downwards, from the largest capacity to the item's weight. The reason was that dp[c - w] must still hold the value from before this item was considered, so the item is not counted twice.

For the unlimited version, you want the opposite. You want dp[c - w] to already include this same item, because that is how an item gets reused. So the loop runs upwards, from the item's weight up to the capacity:

for (int c = w; c <= cap; c++)
    dp[c] = max(dp[c], dp[c - w] + v);

When c is 6, the cell dp[3] has already been updated for this item, so it holds a value that includes one copy of the item. Adding one more copy gives a total with two copies. Each step can add another copy, and no step is blocked.

The program below compares the two loops on the 3 kg bag with capacity 7. The 0/1 version gives 4, and the unlimited version gives 8. The program prints both.

Output:

0/1 answer:       4
unbounded answer: 8

Both loops take O(capacity) time for one item (time that grows with the capacity), so the speed is the same. Only the order of the steps changes what the table means.

The full program

Here is the complete unlimited knapsack. It reads the number of item types, the capacity, and then one line per item with its weight and value. It is the same program as the 0/1 knapsack, with the loop turned upwards.

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 answer is the same 9 as the 0/1 version of this input. That is a coincidence of these numbers. The best unlimited bag for this input happens to use each item at most once. The next example shows a case where reuse changes the table.

Part 2: the table for four items

The four item types are (weight 1, value 1), (3, 4), (4, 5) and (5, 7), with capacity 7. The program below prints the dp row after each item. It also records which item gave each cell its current value, so it can list the items in one best bag.

Output:

start     0 0 0 0 0 0 0 0
item 1  0 1 2 3 4 5 6 7
item 2  0 1 2 4 5 6 8 9
item 3  0 1 2 4 5 6 8 9
item 4  0 1 2 4 5 7 8 9
best value = 9
items in one best bag: 2 2 1

Read the rows one at a time. Each row is the table after one more item type has been allowed. The first row has no items, so every cell is 0. The second row is the table after item 1, which weighs 1 kg and is worth 1. Cell 4 holds 4 because four copies of item 1 weigh 4 kg and are worth 4.

The third row is the table after item 2, which weighs 3 kg and is worth 4. Look at cell 6. It changed from 6 to 8, because two copies of item 2 weigh 6 kg and are worth 8. Cell 7 changed from 7 to 9, because one copy of item 2 plus four copies of item 1 weigh 7 kg and are worth 4 + 4 = 8, while two copies of item 2 plus one copy of item 1 weigh 7 kg and are worth 4 + 4 + 1 = 9. The table keeps the better of the two.

The fourth row, after item 3, does not change anything. Item 3 weighs 4 kg and is worth 5. No capacity from 4 to 7 becomes better when it is used, because the cells already hold at least as much value. The fifth row, after item 4, changes cell 5 from 6 to 7, because one copy of item 4 weighs 5 kg and is worth 7. The other cells stay the same.

The last number in the last row is the answer, 9. The walk back starts at cell 7. The program records that cell 7 was last set by item 2, so it prints item 2 and moves to cell 4. Cell 4 was last set by item 2 again, so it prints item 2 and moves to cell 1. Cell 1 was set by item 1, so the walk prints item 1 and stops at cell 0. The list is 2 2 1, which means two copies of item 2 and one copy of item 1. They weigh 3 + 3 + 1 = 7 kg and are worth 4 + 4 + 1 = 9.

This list is one best bag, not the only one. Item 4 with two copies of item 1 also weighs 5 + 1 + 1 = 7 kg and is worth 7 + 1 + 1 = 9, so it ties. The walk back returns whichever tie the table recorded first.

Why the walk back is safe

The walk back reads lastItem[c], then jumps to c - w. The jump is correct because the cell c - w cannot have improved after the item was added. If it had, adding the item to that better value would beat the value stored at c, and the table would no longer hold the best value for c. A simple check on your own inputs is to add up the chosen items' weights and values. If the weights fit the capacity and the values sum to the printed best value, the list is right.

Part 3: rod cutting

The second problem looks different. A rod is a long, thin piece of metal, and a factory can cut it into pieces of whole-number lengths. Each length has a price. The question is: what cut gives the most money from one rod of length n?

For example, suppose a rod of length 4 has prices 1, 5, 8 and 9 for lengths 1, 2, 3 and 4. You could sell the whole rod for 9. You could cut it into two pieces of length 2 and sell them for 5 + 5 = 10. You could cut it into a piece of length 1 and a piece of length 3 for 1 + 8 = 9. The best of these is 10.

The mapping to the knapsack

Look at what the rod question needs. Each cut uses a piece of some length, and you can use as many pieces of each length as you want, so pieces are unlimited. The rod length plays the role of the bag's capacity. The piece length plays the role of an item's weight. The price plays the role of the value.

Once you see that mapping, the table is the same as the unlimited knapsack. Let best[len] be the most money a rod of length len can earn. The first piece cut off the rod has some length piece from 1 to len. It earns price[piece], and what is left is a rod of length len - piece, which earns best[len - piece]. So:

best[len] = max(best[len], price[piece] + best[len - piece])

The loops are the same as in the unlimited knapsack. The outer loop goes over the piece lengths, the inner loop goes upwards over the rod length, and best[0] is 0 because a rod of length 0 earns nothing.

A small price list

Here is a price list for lengths 1 to 8: 1, 5, 8, 9, 10, 17, 17 and 20. The program below prints the best money for every rod length from 1 to 8. The prices are stored at the index of their length, so price[3] is 8.

Output:

length 1: 1
length 2: 5
length 3: 8
length 4: 10
length 5: 13
length 6: 17
length 7: 18
length 8: 22

Look at length 2. The best is 5, from one piece of length 2. Length 4 is 10, which is two pieces of length 2. Length 6 is 17, which is one piece of length 6, because two pieces of length 3 would make only 16. Length 8 is 22, from a piece of length 2 and a piece of length 6, worth 5 + 17 = 22. A piece of length 8 alone is worth only 20.

The loop order matters here too. The inner loop starts at piece and runs upwards, so a piece length can be used again. For length 4, the table reads best[2], which already includes one piece of length 2, and adds another. That is how two pieces of length 2 are counted.

Recovering the cuts

The program prints the best money, but a person cutting a rod needs the list of cuts. The trick is to store the length of the first piece that gave each rod length its best value. Call it first[len]. To read the cuts, start with the full length, take off first[len], and repeat with what is left.

Type 8 in the Input box, press Enter, then type 1 5 8 9 10 17 17 20 on one line, and press Run.

Output:

best money = 22
pieces: 2 6

The walk takes off the piece of length 2 first, leaving a rod of length 6, and then takes off the piece of length 6. The rod is then empty and the loop stops. The pieces are worth 5 + 17 = 22, which matches the table above.

The loop len -= first[len] only works because first[len] is at least 1 for every length from 1 up. If it were 0, len would never change and the loop would never end. The mistakes section shows what that looks like.

A price list that rewards short pieces

The third example is harder to guess. Suppose a rod of length 4 has prices 3, 1, 1 and 1 for lengths 1 to 4. A piece of length 1 pays 3 per metre, and a piece of length 4 pays only 1. The best plan is four pieces of length 1, earning 4 * 3 = 12.

The program below uses the same table code for this price list. It prints only the best money.

Output:

odd prices, length 4: 12

The table does not need to know that short pieces are better. It compares every choice at each length and keeps the best. A rule like "always cut the most valuable piece first" would fail here, because the most valuable piece is the short one, and the rule would still need the table to find the rest.

Common mistakes

Using the 0/1 loop direction for reuse

If you copy the 0/1 loop into a program that should reuse items, the answer is too small. Here is the rod of length 4 with prices 1, 5, 8 and 9, with the inner loop running downwards.

for (int len = n; len >= piece; len--)
    best[len] = max(best[len], best[len - piece] + price[piece]);

When I ran this loop on that price list, the result for length 4 was 9.

The correct answer is 10, from two pieces of length 2. The downward loop allows only one piece of each length, so the best it can find is the single piece of length 4, worth 9. No error message appears. The program runs and prints a number that looks plausible, which makes this bug easy to miss. Check the direction of the inner loop every time you change between the two problems.

Starting the loop at the wrong index

The upward loop starts at the item's weight, so c - w is never negative. If you start the loop at 0 instead, c - w becomes negative for small capacities. Here is a program with that bug.

int cap = 7, w = 9, v = 12;
vector<int> dp(cap + 1, 0);
for (int c = 0; c <= cap; c++) dp[c] = max(dp[c], dp[c - w] + v);

On the Ubuntu g++ 15 used to test this lesson, the program stops with this message:

/usr/include/c++/15/bits/stl_vector.h:1263: constexpr std::vector<_Tp, _Alloc>::reference std::vector<_Tp, _Alloc>::operator[](size_type) [with _Tp = int; _Alloc = std::allocator<int>; reference = int&; size_type = long unsigned int]: Assertion '__n < this->size()' failed.

The message is long, but the key part is Assertion '__n < this->size()' failed. The index c - w was negative, and the library turned it into a huge number, which is outside the vector. Other compilers may not print a message at all and may read random memory instead. Start every loop at a value that keeps all indexes in range, and check the bounds by hand for the first and last values of c.

Forgetting the base case

The value of an empty bag or a rod of length 0 must be 0. Every cell starts at 0, which works for the "at most capacity" question. If you fill the table with a large negative value so that you can detect impossible cases, you must set dp[0] back to 0. Otherwise every reachable total inherits the negative value, and the answer is negative even when a valid choice exists.

Walking back without the step

The walk-back loop in the rod program must reduce len on each step. If you write the loop as for (int len = n; len > 0; ) cout << first[len]; with no step, the same piece is printed forever. The program then prints numbers without end until it is stopped. Always make the loop body change the variable that controls the loop.

Practice

Each exercise has an answer below it. Try the exercise before you read the answer.

Exercise 1

There is one item type that weighs 2 kg and is worth 3. The bag holds 5 kg. Items can be reused. What is the best value, and how many items are in the bag?

Show the answer

Two items weigh 4 kg and are worth 6. A third item would weigh 6 kg, which is over the limit. The best value is 6, with two items and 1 kg free.

Exercise 2

A rod of length 5 has prices 1, 5, 8, 9 and 10 for lengths 1 to 5. What is the most money you can earn, and which cuts give it?

Show the answer

The best value is 13. It comes from a piece of length 2 and a piece of length 3, worth 5 + 8 = 13. A single piece of length 5 is worth only 10.

Exercise 3

Take the rod program from Part 3, but change the inner loop so it runs from n down to piece. What does it print for a rod of length 4 with prices 1, 5, 8 and 9?

Show the answer

It prints 9. The downward loop allows only one piece of each length, so the best it can find is the single piece of length 4. The correct answer with reuse is 10.

Exercise 4

Items are (weight 2, value 3), (weight 3, value 4) and (weight 4, value 5). The capacity is 6 and items can be reused. What is the best value?

Show the answer

The best value is 9. Three copies of the weight 2 item weigh 6 kg and are worth 3 + 3 + 3 = 9. The other choices reach 8: two copies of the weight 3 item, or one of each of the weight 2 and weight 4 items.

Exercise 5

In the rod program, why must first[len] be at least 1 for every len from 1 to n?

Show the answer

The walk back subtracts first[len] from len on each step. A piece length of 0 would leave len unchanged, so the loop would never end. Every real piece has length 1 or more, and the table only stores a choice when a piece is tried, so every first[len] for len of at least 1 is a real piece length.

Summary

• An unbounded knapsack allows each item to be used any number of times, so the capacity loop runs upwards.
• The 0/1 and unbounded versions differ in loop direction only, and that changes the answer. For one 3 kg item with capacity 7, the answers are 4 and 8.
• A table row for each item type shows how the best value grows as items are added, and the choice array rebuilds one best bag.
• Rod cutting is the unbounded knapsack with rod length as capacity, piece length as weight, and price as value.
• Store the first piece for each length to print the cuts, and make the walk back always shrink the length.
• Check the loop direction and the starting index whenever you move between the 0/1 and unbounded versions.