Show by means of a counterexample that the following greedy

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 n, where 1 lessthanorequalto i lesstahnorequalto n, having maximum density. It then continues by applying the greedy strategy to the remaining piece of length n - i.

Solution

A counterexample used for the greedy strategy:

Length i    1   2    3    4

Price pi      1   20 33 36

         Pi/i    1   10 11   9

Allow the known rod length be 4. From a greedy strategy, we initially cut out a rod of length 3 used for a price of 33, which leaves us by a rod of length 1 of cost 1. The whole price for the rod is 34. The best way is to cut it keen on two rods of length 2 every fetching us 40 dollars.