# CLRS Chapter 15. Dynamic Programming

← chapter 14 ⋮ table of contents ⋮ chapter 16 →

## 15.1. Rod cutting

### Implementation of cut-rod in Python

```
inf = float("inf")
def memoized_cut_rod(p, n):
r = [-inf for _ in range(n+1)]
return memoized_cut_rod_aux(p, n, r)
def memoized_cut_rod_aux(p, n, r):
if r[n] >= 0:
return r[n]
if n == 0:
q = 0
else:
q = -inf
for i in range(1, n+1):
q = max(q, p[i] + memoized_cut_rod_aux(p, n-i, r))
r[n] = q
return q
def bottom_up_cut_rod(p, n):
r = [0 for _ in range(n+1)]
for j in range(1, n+1):
q = -inf
for i in range(1, j+1):
q = max(q, p[i] + r[j-i])
r[j] = q
return r[n]
```

### Exercises

15.1-1.Show that equation (15.4) follows from equation (15.3) and the initial condition .

We first recall (15.3)

and (15.4)

We shall show by induction on that (15.3) with the initial condition implies (15.4).

The base case is precisely the initial condition. We fix an integer and assume that (15.4) holds for all . The inductive hypothesis implies that

as was to be shown.

15.1-2.Show, by means of a counterexample, that the following “greedy” strategy does not always determine an optimal way to cut rods. Define theof a rod of length to be , that is, its value per inch. The greedy strategy for a rod of length cuts off a first piece of length , where , having maximum density. It then continues by applying the greedy strategy to the remaining piece of length .density

Consider the following price table:

length | 1 | 2 | 3 |
---|---|---|---|

price | 0 | 3 | 5 |

Given a rod of length 4, the greedy strategy starts by cutting a rod of length 3, as

This leaves a rod of length 1, and the total price is .

Observe, however, that cutting a rod of length 4 into two rods of length 2 yields the total price of , which is higher than the total price from the greedy strategy. We conclude that the greedy strategy is suboptimal.

15.1-3.Consider a modification of the rod-cutting problem in which, in addition to a price for each rod, each cut incurs a fixed cost of . The revenue associated with a solution is now the sum of the prices of the pieces minus the costs of making the cuts. Give a dynamic-programming algorithm to solve this modified problem.

We implement both the top-down solution and the bottom-up solution.

```
# top-down
inf = float("inf")
def memoized_cut_rod_with_cost(p, n, c):
r = [-inf for _ in range(n+1)]
return memoized_cut_rod_with_cost_aux(p, n, r, c)
def memoized_cut_rod_with_cost_aux(p, n, r, c):
if r[n] > -inf: # allow for negative total price, after the cost
return r[n]
if n == 0:
q = 0
else:
q = -inf
for i in range(1, n+1):
# subtract c here to consider an additional rod
q = max(
q,
p[i] + memoized_cut_rod_with_cost_aux(p, n-i, r, c) - c)
r[n] = q
return r[n]
```

```
# bottom-up
inf = float("inf")
def bottom_up_cut_rod_with_cost(p, n, c):
r = [0 for _ in range(n+1)]
for j in range(1, n+1):
q = -inf
for i in range(1, j+1):
# subtract c here to consider an additional rod
q = max(q, p[i] + r[j-i] - c)
r[j] = q
return r[n]
```

```
>>> A = [0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30]
>>> for i in range(1, 6):
... topdown = rod.memoized_cut_rod(A, i)
... topdown_cost = rod.memoized_cut_rod_with_cost(A, i, 0)
... bottomup = rod.bottom_up_cut_rod(A, i)
... bottomup_cost = rod.bottom_up_cut_rod_with_cost(A, i, 0)
... print((topdown, topdown_cost, bottomup, bottomup_cost))
(1, 1, 1, 1)
(5, 5, 5, 5)
(8, 8, 8, 8)
(10, 10, 10, 10)
(13, 13, 13, 13)
>>> for i in range(1, 6):
... topdown = rod.memoized_cut_rod_with_cost(A, i, 3)
... bottomup = rod.bottom_up_cut_rod_with_cost(A, i, 3)
... print((topdown, bottomup))
(-2, -2)
(2, 2)
(5, 5)
(6, 6)
(7, 7)
```

15.1-4.Modify`memoized-cut-rod`

to return not only the value but the actual solution, too.

Let us begin by studying the extended version of the bottom-up algorithm given in the text. A Python implementation is given below:

```
inf = float("inf")
def extended_bottom_up_cut_rod(p, n):
r = [0 for _ in range(n+1)]
s = [0 for _ in range(n+1)]
r[0] = 0
for j in range(1, n+1):
q = -inf
for i in range(1, j+1):
if q < p[i] + r[j-i]:
q = p[i] + r[j-i]
s[j] = i
r[j] = q
return (r, s)
def print_cut_rod_solution(n, s):
while n > 0:
print(s[n])
n = n - s[n]
```

In addition to computing the maximum, `extended_bottom_up_cut_rod`

records whether the maximum price involves a cutting or not. If it does, `s`

records the location of the first piece to cut off.

Using this idea, we modify `memoized_cut_rod_aux`

as follows:

```
def extended_memoized_cut_rod_aux
```