Rod Cutting Problem
- Tags
- comp-sci
Is a [see page 9, problem] where we have to cut a steel rod of length \( n \) into pieces in order to maximise revenue from selling all the pieces. The cost of each cut is free, rod lengths are an integral number of cm and each rod length \( i \) has its own price.
Rod Cutting Solution example
| Length \( i \) | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| Price \( p_i \) | 1 | 5 | 8 | 9 | 10 | 17 | 17 | 20 | 24 | 30 |
For a rod of length \( n \) there're \( 2^{n-1} \) [see page 10, ways] to cut it. If we [see page 11, let] \( r_i \) be the maximum revenue for a rod of length \( i \), then the profit from such a cut is \( p_i \) and we are left with a rod of length \( n-i \).
This problem demonstrates optimal substructure:
We get an optimal revenue if:
- We make an optimal decision for the first cut of length \( i \), and
- We get an optimal revenue for the remaining rod of length \( n-i \).
This leads to the bellman equation: \[ r_n = \max \{\ p_i + r_{n-i} \; | \; 1 \leq i \leq n \} \]
See [see page 13, bottom up cut rod] and [see page 15, extended bottom up cut rod].