Show that Greedy Algorithm is suboptimal for Gold Rod Question

Question

Consider a greedy algorithm based approach for gold rod question: http://notexponential.com/623/gold-is-a-precious-metal

Show that greedy algorithm based approach is not optimal, by giving a counter example.

Answer 1

When using the greedy method, you will get an approximate answer, which is not always right. For example, due to the length of the wire are given, it is very possible you can't use all wire and has some wire left. In that case, what's has to be left probably be larger than those pieces you choose before.

Here is a simple example: if the wire length is 50.

p1.length = 10, value =60;

p2.length = 20, value =100;

p3.length = 30, value =120;

Using greedy method, you will get p1+p2, value = 160.

However, the right solution is p2+p3, value = 220.