merge n coins with minimum cost to create one single coin

Question

From http://www.geeksforgeeks.org/amazon-interview-set-89/

We have n gold coins. We need to amalgamate all the n coins to create one single coin, we can merge two coins at once. The cost of merging two coins is equal to the value of those coins. How do we ensure that the cost of merging n coins in minimum.

Ex: 5 ,8 , 4, 3, 9, 6
We will merge 3 and 4, cost=7 {Remaining coins: 5,8,9, 6,7}
Then we merge 5 and 6, cost=11 { Remaining coins: 11,8,9,7}
Then we merge 7 and 8, cost=15 { Remaining coins: 11,15,9}
Then we merge 9 and 11, cost=20 { Remaining coins: 20,15}
Then we merge 20 and 15, cost=35 { Remaining coins: 35}
Total cost: 7+11+15+20+35 = 88

If we had merged the coin array {5, 8, 4, 3, 9, 6} in different fashion:

Merging 5 and 8, cost=13 {Remaining coins: 13, 4, 3, 9, 6}
Merging 13 and 4, cost=17 {Remaining coins: 17, 3, 9, 6}
Merging 17 and 3, cost=20 {Remaining coins: 20, 9, 6}
Merging 20 and 9, cost=29 {Remaining coins: 29, 6}
Merging 29 and 6, cost=35 {Remaining coins: 35}
Total cost: 114

As we can see that the cost is less in the first case. how to get the minimum cost of merging all the n coins??

this is just an example, number of coins may of the range 10^9

Answer 1

I've not given this a lot of thought, but off the top of my head, it seems pretty likely that a greedy approach will work: sort the coins and always merge the smallest ones first. The intuition behind this is that you want to "merge" the most expensive coin as infrequently as possible.

If you have one coin, you're done. If you have two coins, you have only one choice. Consider the case with three coins: A < B < C. We can merge these in three ways:

A + B, (A + B) + C => 2A + 2B + C
A + C, (A + C) + B => 2A + 2C + B
B + C, (B + C) + A => 2B + 2C + A

We see that the first option, merging the smallest coins, is best. See Bill's answer for a valuable insight on taking the proof all the way - a comment I contributed is copied here:

You can think of the coins' values as being token frequencies used in Huffman encoding. For very frequent tokens, you want a short code path. I think Bill's pointing out that the "merging" can be thought of as sort of moving up the Huffman tree: the number of times a coin gets merged is its distance from the root. Therefore, the proof of correctness for Huffman's algorithm should apply to the (also) greedy algorithm I describe, which is basically Huffman's, though not for encoding.

Answer 2

Let C_s be the optimal cost of merging S = [s_1, s_2, ..., s_n].

Then if P and Q different only in one element (i.e. p_i = q_i, except for exactly one i), at index j, and p_j < q_j. Then we have that C_P <= C_Q.

Basically, P and Q differ only in a single coin with P having the smaller one. Then optimal merge for P will have lower cost than optimal merge for Q.

This proves that @Patrick87's greedy algorithm is correct.

btw, this is basically a Unary Huffman encoding!