# Exercise 15.1.2

Show, by means of counterexample, that the following "greedy" strategy does not always determine an optimal way to cut rods. Define the

densityof 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$.

Let us have the following options of rod length.

Length | 5 | 4 | 1 |
---|---|---|---|

Cost | 10 | 7 | 1 |

Density | 2 | 1¾ | 1 |

Let's look at a rod of length 8. The greedy algorithm will choose $5 + 1 + 1 + 1$ with value $13$. In comparison, if we just cut it $4 + 4$, we are going to get value $14$.