将n枚硬币与最低成本合并成一枚硬币

Question

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

我们有金币。我们需要合并所有的n个硬币来创造一个单一的硬币，我们可以一次合并两个硬币。合并两枚硬币的成本等于这些硬币的价值。我们如何确保合并n个硬币的成本最小。 例:5 , 8，4，3，9，6我们将合并3和4，cost=7 {剩余硬币: 5,8,9，6,7}然后合并5和6，cost=11 {剩余硬币: 11,8,9,7}然后合并7和8，cost=15 {剩余硬币: 11，15 }然后合并9和11，cost=20 {剩余硬币: 20和15}，cost=35 {剩余硬币: 35}总成本: 7+11+15+20+35 = 88 如果我们以不同的方式合并硬币数组{5、8、4、3、9、6}： 合并5和8，cost=13 {剩余硬币: 13，4，3，9，6}合并13和4，cost=17 {剩余硬币: 17，3，9，6}合并17和3，cost=20 {剩余硬币: 20，9，6}合并20和9，cost=29 {剩余硬币: 29，6}合并29和6，cost=35 {剩余硬币: 35}总成本: 114 我们可以看到，在第一种情况下，成本较低。如何获得所有n枚硬币合并的最小成本？ 这只是一个例子，硬币的数量可能在10^9之间。

Answer 1

我没有仔细考虑过这个问题，但从我的头顶上看，似乎有一种贪婪的方法会奏效:对硬币进行排序，并且总是先合并最小的硬币。这背后的直觉是，你想要“合并”最昂贵的硬币尽可能少。

如果你有一枚硬币，你就完了。如果你有两个硬币，你只有一个选择。考虑三个硬币的情况:A

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

我们认为，第一个选择，合并最小的硬币，是最好的。请参阅Bill的回答，以获得关于一路获取证据的宝贵见解--我在这里提供的一条评论抄袭如下：

您可以将硬币的值看作是霍夫曼编码中使用的令牌频率。对于非常频繁的标记，您需要一个简短的代码路径。我认为比尔指出，“合并”可以被看作是在赫夫曼树上移动:硬币被合并的次数是它与根的距离。因此，对Huffman算法的正确性证明应该适用于我描述的(也)贪婪算法，它基本上是Huffman的，但不是编码的。

Answer 2

假设C_s是合并S = [s_1, s_2, ..., s_n]的最佳成本。

如果P和q仅在一个元素(即p_i = q_i，除了一个I之外)不同，则在指数j和p_j < q_j处。那我们就有那个C_P <= C_Q了。

基本上，P和Q只在一枚硬币中不同，P有较小的硬币。P的最优合并比Q的最优合并具有更低的成本。

这证明@Patrick87 87的贪婪算法是正确的。

顺便说一下，这基本上是一种一元赫夫曼编码！