Greedy algorithm or dynamic programming?

3
votes

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.

3
algorithmdynamic-programminggreedy
Does gluing 2 pieces add to the length? – SGM1
What you mean? When you glue two pieces of length a and b you get new piece of length a + length b. – piternet
Two sticks can be glued on top of each other, that's why I asked. Odd to have glue amount dependent on length in that case IMHO, practically speaking. – SGM1
Are you sure there's an efficient solution to this problem? I'd have guessed it's NP hard. For example if you change the problem slightly, making all the glue free except for the last gluing, then the problem is to find a subset of the lengths which is as close as possible to sum(x_i)/2, which is the partition problem. That doesn't mean this problem is also NP hard, but it's suggestive. – Paul Hankin
This sounds like it maps to the making-change-with-a-minimal-number-of-coins problem. For some sets of coin denominations, it can be solved with a greedy algorithm, but not for others. I recently learned that there's a paper that describes an algorithm to determine, in finite time, if the greedy algorithm is sufficient for a given set of coin denominations. – Adrian McCarthy

3 Answers

4
votes

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.

0
votes

It looks like there are no optimal greedy algorithm and no general dynamic programming solution. I think it is NP-hard and I explain why.

Let analyse problem. We have N elements. Let split this set into two subsets with X and Y elements. At first we glue all elements in X subset and then glue all elements in Y subset in some way (like divide and conqueror technique). And in the last glueing we should glue 2 elements that represent X and Y subsets. What the smallest amount of glue we need in this last gluing? When the difference of sums of X elements and Y elements is the smallest! We represent this problem as recursive partition problem which is NP hard itself

0
votes

The greedy algorithm will surely not work as Briguy37 said because the greedy local optimal solution will not give you a globally optimal solution in this case.

However, this problem is an NP class problem, It cannot be solved using dynamic programming. You need to work on a brute force approach which would take exponential time. Please look at the below tree for one part of this problem where we start with size 1. Clearly we don't see any logical overlapping subproblems which we can generalize into a dynamic programming approach.

Tree for starting with size 1