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 density of 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.

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