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.
Because a local maximum is not always a global maximum.

The length 3 rod is the most price-for-length effective single rod piece. But the optimization goal isn't to find the best price-to-length ratio for a single piece, it's to find the best total price for how much rod we actually have! Once the greedy algorithm chooses the shiniest, most appealing first piece, it is now stuck for the rest of the problem with a highly suboptimal remaining length according to the highly nonlinear price table.

In general, most optimization problems cannot be solved optimally by a greedy strategy. Those that can tend to have some exceptional property that guarantees that a local maximum will also be a global maximum.