The unbounded knapsack pattern

Lesson · 9 min read · Dynamic programming · Pattern: unbounded knapsack

Pieces can be reused any number of times. The answer for a total reads the answers for that total minus each piece.

The pattern

Cutting a rod into pieces of any lengths, splitting an integer into parts, paying with unlimited coins: each piece type can be used again, so the state is just the total, and the recurrence tries every piece as the last one.

Unbounded pattern

best[t]

= opt over pieces p with size(p) ≤ t of value(p) ⊕ best[t − size(p)].

loop

totals upwards (or pieces outside and totals upwards).

Worked example: cutting a rod

A rod of length 8; a piece of length L sells for price[L]. best[n] = max over the first piece L of price[L] + best[n − L].

Prices 1, 5, 8, 9, 10, 17, 17, 20 for lengths 1 to 8.

Step 1 / 9

best
00·1·2·3·4·5·6·7·8
Base case: best[0] = 0.
Step 2 / 9

best
0011·2·3·4·5·6·7·8
Length 1: best first piece 1 (price 1) + best[0] = 1.
Step 3 / 9

best
001152·3·4·5·6·7·8
Length 2: best first piece 2 (price 5) + best[0] = 5.
Step 4 / 9

best
00115283·4·5·6·7·8
Length 3: best first piece 3 (price 8) + best[0] = 8.
Step 5 / 9

best
00115283104·5·6·7·8
Length 4: best first piece 2 (price 5) + best[2] = 10.
Step 6 / 9

best
00115283104135·6·7·8
Length 5: best first piece 2 (price 5) + best[3] = 13.
Step 7 / 9

best
00115283104135176·7·8
Length 6: best first piece 6 (price 17) + best[0] = 17.
Step 8 / 9

best
00115283104135176187·8
Length 7: best first piece 1 (price 1) + best[6] = 18.
Step 9 / 9

best
00115283104135176187228
Length 8: best first piece 2 (price 5) + best[6] = 22. best[8] = 22: pieces 2 + 6.

How to recognise it

Unlimited supply of each kind.
The order of pieces does not matter for an optimum (it does for counting: see the next pattern).

TimeO(kinds · target)

SpaceO(target)

The problems in this module: