Easy Problemsoptimizationknapsack

Cutting a Rod

Given a rod of length n and a price list for pieces of every integer length up to n, cut the rod into pieces, or leave it whole, to maximize the total sale price of the resulting pieces.

Do this lesson first: coin change

Example input

price = [1, 5, 8, 9] for lengths 1 to 4, n = 4

Expected output

10

Break it down

Answer each question out loud before you open it. Getting it wrong here is the useful part. A revealed answer you never guessed at teaches you nothing.

dp[i][L] is the best total price for a rod of length L when the only piece lengths you may cut are 1 through i. Row i widens the menu of piece lengths by one, and column L is the length of rod being sold, so the bottom-right cell, every length allowed and the whole rod, is the answer. Leaving the rod whole is not a special case: it is cutting one piece of length n, which only the last row allows. Throughout, price[i] means the price of a piece of length i, which the snippet's 0-indexed array stores as price[i - 1].

dp[i][L] = max(dp[i - 1][L], price[i] + dp[i][L - i]), the second only when i <= L

Ask about the longest piece length this row allows, i. Either the best cut uses no piece of length i, and then it is the best cut with lengths up to i - 1: the cell above. Or it uses at least one: sell that piece for price[i], and cut the remaining L - i as well as possible with lengths up to i STILL allowed, because another piece of length i may come out of it too. That is the cell i columns to the left in the same row. Take the better of the two. This is unbounded-knapsack exactly, with piece lengths as the items, lengths as weights and prices as values, which is why this site files it with the knapsacks rather than with the one-row version most textbooks print.

Row 0 is the only base row, and it is 0 everywhere. At column 0 that is exact: a rod of length 0 sells for nothing. At a positive length it is a stand-in: with no piece lengths allowed no cut exists, and the exact value would be minus infinity. 0 is safe here because the only cells that read row 0 are row 1's no-piece options, and row 1's other option is L × price[1], which is above 0 for every L > 0 because price[1] is positive, so the stand-in never wins at a positive length. Rows 2 and later never read row 0 at all. Fill row by row, left to right within a row: the with-a-piece case reads its own row further left, so that cell must already be final. The slider here moves both axes at once, because a longer rod needs one more column for its length and one more row for the new piece length it allows.

Tabulation over (n + 1) × (n + 1) cells. Each row reads only itself and the row above, so one row of n + 1 values is enough: for each piece length i, sweep L upward and keep the larger of the old value and price[i] + best[L - i]. Swap those two loops, rod length outside and piece length inside, and you get the one-row recurrence most textbooks print, best[L] = max over i <= L of price[i] + best[L - i]. For a max the loop order does not change the answer, which is the opposite of coin-change-count-ways, where swapping the same two loops turns combinations into ordered sequences.

Time O(n^2)Space O(n^2), reducible to O(n) with one row

Fill the table

The table pauses before each cell you have to supply. Type the value the recurrence gives, and the write animation confirms it.

Step not started

Press start. The animation stops at every cell YOUR recurrence must fill.

Row 0 is the only base row, and it is 0 everywhere. At column 0 that is exact: a rod of length 0 sells for nothing. At a positive length it is a stand-in: with no piece lengths allowed no cut exists, and the exact value would be minus infinity. 0 is safe here because the only cells that read row 0 are row 1's no-piece options, and row 1's other option is L × price[1], which is above 0 for every L > 0 because price[1] is positive, so the stand-in never wins at a positive length. Rows 2 and later never read row 0 at all. Fill row by row, left to right within a row: the with-a-piece case reads its own row further left, so that cell must already be final. The slider here moves both axes at once, because a longer rod needs one more column for its length and one more row for the new piece length it allows.

Rows ↓
Cols →

0

1

2

3

4

none

0

len 1

0

1

2

3

4

len 2

0

1

5

6

10

len 3

0

1

5

8

10

len 4

0

1

5

8

10

Rows ↓row i: piece lengths 1 to i allowed

Cols →rod length L: best price for it

cutting-a-rod.ts

1function cutRod(price, n) {
2 const dp = Array.from({ length: n + 1 }, () => new Array(n + 1).fill(0));
3 // row 0: no piece lengths allowed, nothing sold
4 for (let i = 1; i <= n; i++) {
5 for (let L = 0; L <= n; L++) {
6 dp[i][L] = dp[i - 1][L];
7 if (i <= L) dp[i][L] = Math.max(dp[i][L], price[i - 1] + dp[i][L - i]);
8 }
9 }
10 return dp[n][n];
11}

Base caseComputedBeing readAnswer

The code, the trap, the variations

cutting-a-rod.ts

1function cutRod(price, n) {
2 const dp = Array.from({ length: n + 1 }, () => new Array(n + 1).fill(0));
3 // row 0: no piece lengths allowed, nothing sold
4 for (let i = 1; i <= n; i++) {
5 for (let L = 0; L <= n; L++) {
6 dp[i][L] = dp[i - 1][L];
7 if (i <= L) dp[i][L] = Math.max(dp[i][L], price[i - 1] + dp[i][L - i]);
8 }
9 }
10 return dp[n][n];
11}

Where people go wrong

Trusting the best-looking piece. At length 4 the whole rod sells for 9, and the length with the best price per unit is 3 (8 for 3, about 2.67 a unit, against 2.5 for length 2), so cutting the densest piece first gives 8 + 1 = 9. Both lose to two pieces of length 2 for 10, which neither rule ever looks at. The second trap is reading the with-a-piece case from the row above: that lets each length be cut at most once, and at length 4 it answers 9, because 5 + 5 needs the length-2 piece twice.

Allow at most one piece of each length.
The with-a-piece case reads the row above instead of the current row, which turns this into zero-one-knapsack with lengths as weights. At length 4 the answer drops from 10 to 9, because two pieces of length 2 are no longer allowed. State and fill order do not change.
Only some piece lengths are for sale, not every length up to n.
Only those lengths get rows, and a row's with-a-piece option steps left by that row's own length and adds that length's price, rather than by the row number. The max and the fill order stay. Row 0 changes too: a length that cannot be cut exactly into allowed pieces now exists, so decide whether leftover rod may be thrown away (keep the zeros) or not (make them minus infinity, so an exact cut is required).
Report the cuts, not just the price.
Fill the same table, then walk back from the corner: if a cell equals the one above, no piece of length i was used, so step up; otherwise record a piece of length i and step i columns left in the same row. printing-items-in-zero-one-knapsack teaches that walk on a 0/1 table.

Painting Fence Algorithm Jump Game