Rod Cutting

Intro

Zonvolt Inc. is a firm that specializes in cutting. They received a batch of long steel rods. Now, they have to cut them into smaller pieces and sell them. Suppose each cut is free, how should they cut in order to maximize their profit?

Question ()

Given a rob of length n and a price table, determine the maximum possible revenue.

Price Table

| Length | 1 | 2 | 3 | 4 | 5  | 6  | 7  | 8  | 9  | 10 |
| Price  | 1 | 5 | 8 | 9 | 10 | 17 | 17 | 20 | 24 | 30 |

Example

I: n=4, price_table
O: 10

Analysis

1. Define optimal subproblems
rev(n) = max revenue for rod of length n
2. Recurrence - solve by suffix
rev(n) = max(price[i] + rev(n-i)) for i from 1 to n
3. Topo order
4. Init base cases
5. Final answer

Brute Force Approach

We can do a dfs to decompose n=4 and find all possible ways to cut

price(1+1+1+1) = 4
price(1+1+2) = 7
price(1+2+1) = 7
price(1+3) = 9
price(2+2) = 10
price(3+1) = 9
price(4) = 9

At each unit, we decide whether to cut or not to cut. In total, there are $2^{n-1}$ possible ways of cutting.

Top-down Code

func rod(price, n)
    // base case
    if (n == 0) return 0
    // recurrence
    rev = MIN_VALUE
    for i from 1 to n
        rev = max(rev, rod(price[i] + rod(price, n-i)))
    end for
    // final answer
    return rev
end func

The recurrence for this function is $T(n) = \sum\limits_{j=0}^{n-1}{T(j)} + O(1)$ .

Runtime Analysis

Theorem: For any $n \in \mathbb{N}, T(n) = 2^n.$

Proof: Base case $n = 0: T(0) = 1$ Inductive hypothesis: Assume $T(n-1) = 2^{n-1}$ Inductive step: $\begin{aligned} T(n) & = \sum\limits_{j=0}^{n-1}{T(j)} + 1 \\ & = \sum\limits_{j=0}^{n-2}{T(j)} + T(n-1) + 1 \\ & = T(n-1) - 1 + T(n-1) + 1 \\ & = 2T(n-1) \text{ by I.H.} \\ & = 2^n \end{aligned}$

Top-down + Memoization

Conclusion

"My conjecture is that you actually know more computer science than you think." - David Malan

When I was writing the brute force approach, my brain automatically avoided writing the repetitive cuts. But the program procedure doesn't know. So we gonna program it.

Reference

CLRS 15.1 Rod Cutting

PreviousWood Cut NextWord Break

Last updated 5 years ago

1. Define optimal subproblems rev(n) = max revenue for rod of length n 2. Recurrence - solve by suffix rev(n) = max(price[i] + rev(n-i)) for i from 1 to n 3. Topo order 4. Init base cases 5. Final answer

Brute Force Approach

We can do a dfs to decompose n=4 and find all possible ways to cut

price(1+1+1+1) = 4
price(1+1+2) = 7
price(1+2+1) = 7
price(1+3) = 9
price(2+2) = 10
price(3+1) = 9
price(4) = 9

At each unit, we decide whether to cut or not to cut. In total, there are

2^{n-1}

possible ways of cutting.

Top-down Code

func rod(price, n)
    // base case
    if (n == 0) return 0
    // recurrence
    rev = MIN_VALUE
    for i from 1 to n
        rev = max(rev, rod(price[i] + rod(price, n-i)))
    end for
    // final answer
    return rev
end func

The recurrence for this function is

T(n) = \sum\limits_{j=0}^{n-1}{T(j)} + O(1)

Runtime Analysis

Theorem: For any

n \in \mathbb{N}, T(n) = 2^n.

Proof: Base case

n = 0: T(0) = 1

Inductive hypothesis: Assume

T(n-1) = 2^{n-1}

Inductive step:

\begin{aligned} T(n) & = \sum\limits_{j=0}^{n-1}{T(j)} + 1 \\ & = \sum\limits_{j=0}^{n-2}{T(j)} + T(n-1) + 1 \\ & = T(n-1) - 1 + T(n-1) + 1 \\ & = 2T(n-1) \text{ by I.H.} \\ & = 2^n \end{aligned}