# Why this greedy algorithm fails in rod cutting problem?

Recall the rod cutting problem.

Given a rod of length $$n$$ inches and a table of prices $$p_{i}$$ for $$i=1,2,3,4,\,.\,.\,.$$ determine the maximum revenue $$r_n$$ obtainable by cutting up the rod and selling the pieces. You may assume no cutting cost.

The following is a question from CLRS 15.1-2.

Show, by means of a 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≤i≤n, having maximum density. It then continues by applying the greedy strategy to the remaining piece of length n-i.

Consider prices up to length $$4$$ are $$p_1=1, p_2=5, p_3= 8, p_4 = 9$$ respectively. So, densities are $$d_1=1, d_2 = 2.5, d_3= 2.67, d_4 = 2.25$$ respectively.

If we are given a rod of length $$4,$$ then an optimal way of cutting the rod to maximize revenue is $$2$$ pieces of length $$2$$ each, generating $$5+5 = 10.$$

However, greedy algorithm above will suggest cutting the rod into 2 pieces of length $$3$$ and $$1$$, generating revenue $$8+1=9.$$

I obtain this example by merely following the same prices given in CLRS but do not understand why such greedy algorithm fails to provide optimal way of cutting the rod.