rod-cutting.md (2054B)
1 +++ 2 title = "Rod cutting" 3 template = "page-math.html" 4 +++ 5 6 # Rod cutting 7 8 Problem: 9 Rod of length n, table of prices. Determine maximum possible revenue. 10 11 <table> 12 <tr> <td>i</td> <td>1</td> <td>2</td> <td>3</td> <td>4</td> </tr> 13 <tr> <td>p</td> <td>1</td> <td>5</td> <td>8</td> <td>9</td> </tr> 14 </table> 15 16 Solution: 17 Total 2n-1 possibilities of cutting. 18 19 Create a table: 20 21 | i | 1 | 2 | 3 | 4 | 22 | --- | --- | --- | --- | --- | 23 | Max profit | | | | | 24 25 $C(i)=\max{\{V_k+C(i-k)\}}\\;|\\;_{1 \leq k \leq i}$ 26 27 Then solve: 28 29 $\begin{aligned} 30 C(1) &= 1\\\\ 31 C(2) &= \begin{cases}V_1+C(1)=1+1=2\\\\ V_2=5\end{cases} \\\\ 32 5 &> 2 \\\; \therefore 5 \\\\ 33 C(3) &= \begin{cases}V_1+C(2)=1+5=6\\\\ V_2=C(1)=5+1=6\\\\ V_3=8\end{cases} \\\\ 34 8 &> 6 \therefore 8 \\\\ 35 C(4) &= \begin{cases}V_1+C(3)=1+8=9\\\\ V_2+C(2)=5+5=10\\\\ V_3+C(1)=8+1=9\\\\ V_4=9\end{cases} \\\\ 36 10 &> 9 \therefore 10 37 \end{aligned}$ 38 39 | i | 1 | 2 | 3 | 4 | 40 | --- | --- | --- | --- | --- | 41 | Max profit | 1 | 5 | 8 | 10 | 42 43 Highest profit is 10. 44 - Optimal solution for $C(4) = V_2 + C(2)$ 45 - Optimal solution for $C(2) = V_2$ 46 47 Profit of 10 can be reached by cutting rod into two pieces of size 2. 48 49 Worst-case complexity: recursive algorithm gives $T(n)=2^n$ 50 51 DP gives $T(n)=O(n^2)$ after solving $\sum_{j=1}^{n}j$ 52 53 Extending: 54 55 “Density is pi/i. Greedy algorithm always takes highest density. Explain why it doesn’t always work.” 56 57 e.g. rod of length for, 2+2 is best solution. 58 59 | i | 1 | 2 | 3 | 4 | 60 | --- | --- | --- | --- | --- | 61 | p | 0.1 | 3 | | 0.1 | 62 | p/i | 0.1 | 1.5 | | 0.025 | 63 64 $\begin{aligned}p_2+p_2&=6\\\\ 65 \therefore p_3+p_1 &< 6\\\\ 66 p_3+0.1&<6\\\\ 67 p_3&<5.9 68 \end{aligned}$ 69 70 Greedy takes based on density 71 72 $\begin{aligned}\frac{p_3}{3}&>1.5\\\\ 73 p_3&>4.5\\\\ 74 \therefore 4.5<&p_3<5.9\\\\ 75 \text{e.g. } p_3&=4.8 76 \end{aligned}$ 77 78 79 | i | 1 | 2 | 3 | 4 | 80 | --- | --- | --- | --- | --- | 81 | p | 0.1 | 3 | 4.8 | 0.1 | 82 | p/i | 0.1 | 1.5 | 1.6 | 0.025 | 83 84 Greedy takes 4.8+0.1=4.9, which is less than 3+3=6 from DP approach.