CLRS Chapter 15. Dynamic Programming

chapter 14table of contentschapter 16

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 .

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 the density of 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 .

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