Skip to content

15.1 Rod cutting

15.1-1

Show that equation $\text{(15.4)}$ follows from equation $\text{(15.3)}$ and the initial condition $T(0) = 1$.

We can verify that $T(n) = 2^n$ is a solution to the given recurrence by the substitution method. We note that for $n = 0$, the formula is true since $2^0 = 1$. For $n > 0$, substituting into the recurrence and using the formula for summing a geometric series yields

$$ \begin{aligned} T(n) & = 1 + \sum_{j = 0}^{n - 1} 2^j \\ & = 1 + (2^n - 1) \\ & = 2^n. \end{aligned} $$

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 \le i \le n$, having maximum density. It then continues by applying the greedy strategy to the remaining piece of length $n - i$.

Here is a counterexample for the "greedy" strategy:

$$ \begin{array}{c|cccc} \text{length $i$} & 1 & 2 & 3 & 4 \\ \hline \text{price $p_i$} & 1 & 20 & 33 & 36 \\ p_i / i & 1 & 10 & 11 & 1 \end{array} $$

Let the given rod length be $4$. According to a greedy strategy, we first cut out a rod of length $3$ for a price of $33$, which leaves us with a rod of length $1$ of price $1$. The total price for the rod is $34$. The optimal way is to cut it into two rods of length $2$ each fetching us $40$ dollars.

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.

1
2
3
4
5
6
7
8
9
MODIFIED-CUT-ROD(p, n, c)
    let r[0..n] be a new array
    r[0] = 0
    for j = 1 to n
        q = p[j]
        for i = 1 to j - 1
            q = max(q, p[i] + r[j - i] - c)
        r[j] = q
    return r[n]

The major modification required is in the body of the inner for loop, which now reads $q = \max(q, p[i] + r[j - i] - c)$. This change reflects the fixed cost of making the cut, which is deducted from the revenue. We also have to handle the case in which we make no cuts (when $i$ equals $j$); the total revenue in this case is simply $p[j]$. Thus, we modify the inner for loop to run from $i$ to $j - 1$ instead of to $j$. The assignment $q = p[j]$ takes care of the case of no cuts. If we did not make these modifications, then even in the case of no cuts, we would be deducting $c$ from the total revenue.

15.1-4

Modify $\text{MEMOIZED-CUT-ROD}$ to return not only the value but the actual solution, too.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
MEMOIZED-CUT-ROD(p, n)
    let r[0..n] and s[0..n] be new arrays
    for i = 0 to n
        r[i] = -
    (val, s) = MEMOIZED-CUT-ROD-AUX(p, n, r, s)
    print "The optimal value is" val "and the cuts are at"
    j = n
    while j > 0
        print s[j]
        j = j - s[j]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
MEMOIZED-CUT-ROD-AUX(p, n, r, s)
    if r[n]  0
        return r[n]
    if n == 0
        q = 0
    else q = -
        for i = 1 to n
            (val, s) = MEMOIZED-CUT-ROD-AUX(p, n - i, r, s)
            if q < p[i] + val
                q = p[i] + val
                s[n] = i
    r[n] = q
    return (q, s)

$\text{PRINT-CUT-ROD-SOLUTION}$ constructs the actual lengths where a cut should happen. Array entry $s[i]$ contains the value $j$ indicating that an optimal cut for a rod of length $i$ is $j$ inches. The next cut is given by $s[i - j]$, and so on.

15.1-5

The Fibonacci numbers are defined by recurrence $\text{(3.22)}$. Give an $O(n)$-time dynamic-programming algorithm to compute the nth Fibonacci number. Draw the subproblem graph. How many vertices and edges are in the graph?

1
2
3
4
5
6
FIBONACCI(n)
    let fib[0..n] be a new array
    fib[0] = fib[1] = 1
    for i = 2 to n
        fib[i] = fib[i - 1] + fib[i - 2]
    return fib[n]

$\text{FIBONACCI}$ directly implements the recurrence relation of the Fibonacci sequence. Each number in the sequence is the sum of the two previous numbers in the sequence. The running time is clearly $O(n)$.

The subproblem graph consists of $n + 1$ vertices, $v_0, v_1, \ldots, v_n$. For $i = 2, 3, \ldots, n$, vertex $v_i$ has two leaving edges: to vertex $v_{i - 1}$ and to vertex $v_{i - 2}$. No edges leave vertices $v_0$ or $v_1$. Thus, the subproblem graph has $2n - 2$ edges.