Greedy algorithm or dynamic programming?

Question

There is list l = [x_1, ..., x_n] given. Every element of the list is the length of some piece of wood. To glue two pieces of wood, of lengths a and b you need max(a,b) of glue. After glueing, you got one piece of wood of length a+b. Compute minimum amount of glue to glue all the pieces.

Do you think greedy algorithm works here? I can't think of any example. Saying greedy algorithm I mean: take two pieces of minimal length, glue them and do that until all pieces are glued. Using some priority queue, this can be done in O(n log n) complexity.

Does that work? If not, give me please some example of list l, which can be glued in smaller amount of glue than greedy algorithm would say.

Answer 1

The greedy algorithm won't always be optimal. A counter example is [1, 2, 2, 3], for which the greedy algorithm will use 10 units of glue and the optimal will use 9 units.

Greedy Algorithm:

1-2 = 2 glue
2-3 = 3 glue
3-5 = 5 glue
---------------
total = 10 glue

Optimal:

2-2 = 2 glue
1-3 = 3 glue
4-4 = 4 glue
--------------
total = 9 glue

Dynamic programming it is.