###### tags: `ADA 5.2` `Rod Cutting Problem`
# ADA 5.2: Rod Cutting Problem
- Textbook Chapter 15.1 - Rod Cutting
## Rod Cutting Problem
- Input: a rod of length n and a table of prices $p_i$ for $i=1,..,n$
- Output: the maximum revenue $r_n$ obtainable by cutting up the rod and selling the pieces (and the list of cut pieces)
## Brute-Force Algorithm
- A rod with the $length=4$
- A rod with the $length=n$
- For each integer position, we can choose “cut” or “not cut”
- There are $n-1$ positions for consideration
- The total number of cutting results is $2^{n-1}=\Theta(2^{n-1})$
## Recursive Thinking
- We use a recursive function to solve the subproblems
- If we know the answer to the subproblem, can we get the answer to the original problem?
- $r_n$: the maximum revenue obtainable for a rod of length $n$
- Optimal substructure - an optimal solution can be constructed from optimal solutions to subproblems
## Recursive Algorithms
- Version 1
- Version 2
- try to reduce the number of subproblems → focus on the **left-most** cut
## Recursive Procedure
- Focus on the left-most cut
- assume that we always cut **from left to right** → the first cut
## Naive Recursion Algorithm
- $r_n=max_{1\leq i\leq n}(p_i+r_{n-i})$
```python=
Cut-Rod(p, n)
// base case
if n == 0
return 0
// recursive case
q = -∞
for i = 1 to n
q = max(q, p[i] + Cut-Rod(p, n - i))
return q
```
- $T(n)$: time for running **Cut-Rod(p, n)**
$$
T(n) =
\begin{cases}
\Theta(1), & \text{if $n$ = 1} \\
\Theta(1) + \Sigma_{i=0}^n T(n-i), & \text{if $n$ $\ge$ 2}
\end{cases}
\implies T(n)=\Theta(2^n)
$$
## Dynamic Programming
- Idea: use space for better time efficiency
- Rod cutting problem has overlapping subproblems and optimal substructures → can be sovled by DP
- When the number of subproblems is polynomial, the time complexity is polynomial using DP
- DP algorithm
- Top-down: solve overlapping subproblems recursively with memoization
- Bottom-up: build up solutions to larger and larger subproblems
- Top-Down with Memoization
- Better when some subproblems not be solved at all
- Solve only the required parts of subproblems
- Bottom-Up with Tabulation
- Better when all subproblems must be solved at least once
- Typically outperform top-down method by a constant factor
- No overhead for recursive calls
- Less overhead for maintaining the table
## Algorithm for Rod Cutting Problem
### Top-Down with Memoization
```python=
Memoized-Cut-Rod(p, n)
// initialize memo (an array r[] to keep max revenue)
r[0] = 0
for i = 1 to n // Θ(n)
r[i] = -∞ // r[i] = max revenue for rod with length = i
return Memoized-Cut-Rod-Aux(p, n, r)
Memoized-Cut-Rod-Aux(p, n, r)
if r[n] >= 0
return r[n] // return the saved solution, Θ(1)
q = -∞
for i = 1 to n // Θ(n²)
q = max(q, p[i] + Memoized-Cut-Rod-Aux(p, n-i, r))
r[n] = q // update memo
return q
```
- $T(n)$: time for running **Memoized-Cut-Rod(p, n)** $\rightarrow T(n)=\Theta(n^2)$
### Bottom-Up with Tabulation
```python=
Bottom-Up-Cut-Rod(p, n)
r[0] = 0
for j = 1 to n // compute r[1], r[2], ... in order, Θ(n²)
q = -∞
for i = 1 to j
q = max(q, p[i] + r[j - i])
r[j] = q
return r[n]
```
- $T(n)$: time for running **Bottom-Up-Cut-Rod(p, n)** $\rightarrow T(n)=\Theta(n^2)$
- Add an array to keep the cutting positions $cut$
```python=
Extended-Bottom-Up-Cut-Rod(p, n)
r[0] = 0
for j = 1 to n // compute r[1], r[2], ... in order, Θ(n²)
q = -∞
for i = 1 to j
if q < p[i] + r[j - i]
q = p[i] + r[j - i]
cut[j] = i // the best first cut for length j rod
r[j] = q
return r[n], cut
Print-Cut-Rod-Solution(p, n)
(r, cut) = Extended-Bottom-Up-Cut-Rod(p, n)
while n > 0
print cut[n]
```
## Informal Running Time Analysis
- Approach 1: approximate via (#subproblems) * (#choices for each subproblem)
- For rod cutting
- #subproblems = n
- #choices for each subproblem = O(n)
- T(n) is about O(n²)
- Approach 2: approximate via subproblem graphs
- The size of the subproblem graph allows us to estimate the time complexity of the DP algorithm
- A graph illustrates the set of subproblems involved and how subproblems depend on another $G=(V,E)$ (E: edge, V: vertex)
- $|V|$: #subproblems
- $|E|$: sum of #subproblems are needed for each subproblem
- Time complexity: linear to $O(|E|+|V|)$
## Dynamic Programming Procedure
1. **Characterize the structure** of an optimal solution
1. Overlapping subproblems: revisit same subproblems
2. Optimal substructure: an optimal solution to the problem contains within it optimal solutions to subproblems
2. **Recursively** define the value of an optimal solution
1. Express the solution of the original problem in terms of optimal solutions for subproblems
3. **Compute the value** of an optimal solution
1. Typically in a bottom-up fashion
4. **Construct an optimal solution** from computed information
1. Step 3 and 4 may be combined
## Revisit DP for Rod Cutting Problem
### Step 1: Characterize an OPT Solution
- Step 1-Q1: What can be the subproblems?
- Subproblems: **Cut-Rod(i)**, rod cutting problem with length i rod
- Step 1-Q2: Does it exhibit optimal structure? (an optimal solution can be represented by the optimal solutions to subproblems)
- Proved by contradiction
### Step 2: Recursively Define the Value of an OPT Solution
- Recursively define the value
$$
r_i =
\begin{cases}
0 & \text{if $i$ = 0} \\
max_{1\leq j\leq i}(p_j+r_{i-j}) & \text{if $i$ $\ge$ 1}
\end{cases}
$$
### Step 3: Compute Value of an OPT Solution
```python=
Bottom-Up-Cut-Rod(p, n)
r[0] = 0
for j = 1 to n // compute r[1], r[2], ... in order, Θ(n²)
q = -∞
for i = 1 to j
q = max(q, p[i] + r[j - i])
r[j] = q
return r[n]
```
- $T(n)=\Theta(n^2)$
### Step 4: Construct an OPT Solution by Backtracking
```python=
Extended-Bottom-Up-Cut-Rod(p, n)
r[0] = 0
for j = 1 to n // compute r[1], r[2], ... in order, Θ(n²)
q = -∞
for i = 1 to j
if q < p[i] + r[j - i]
q = p[i] + r[j - i]
cut[j] = i // the best first cut for length j rod
r[j] = q
return r[n], cut
```
- $T(n)=\Theta(n^2)$
```python=
Print-Cut-Rod-Solution(p, n)
(r, cut) = Extended-Bottom-Up-Cut-Rod(p, n)
while n > 0
print cut[n]
n = n - cut[n] // remove the first piece
```
- $T(n)=\Theta(n)$
Sign in with Wallet
Connect another wallet