# CLRS Chapter 15. Dynamic Programming

source code directory

## 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 $T(0) = 1$.

We first recall (15.3)

and (15.4)

We shall show by induction on $n$ that (15.3) with the initial condition $T(0) = 1$ implies (15.4).

The base case $n=1$ is precisely the initial condition. We fix an integer $N > 1$ and assume that (15.4) holds for all $% $. The inductive hypothesis implies that

as was to be shown. $\square$

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 the density of a rod of length $i$ to be $p_i/i$, that is, its value per inch. The greedy strategy for a rod of length $n$ cuts off a first piece of length $i$, where $1 \leq i \leq n$, having maximum density. It then continues by applying the greedy strategy to the remaining piece of length $n-i$.

Consider the following price table:

length $i$ 1 2 3
price $p_i$ 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 $5 + 0 = 5$.

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

15.1-3. Consider a modification of the rod-cutting problem in which, in addition to a price $p_i$ for each rod, each cut incurs a fixed cost of $c$. 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