arrays - 切割一根棍子，使成本最小化

问题描述

你必须把一根有长度的棍子切成l几块。片段必须有长度a1, ..., an，其中ai是整数。切割的成本等于制作它的棍子的长度。设计一种算法，找到这种切割n碎片的最小可能价格。例如，考虑一根长度15和所需件长度1, 2, 3, 4, 5。你可以按照给定的顺序剪断木棍。第一次切割会花费15，因为棍子是有长度的15。第二次削减将花费14，因为进行切割的剩余木棍的长度为 15 - 1 = 14。第三次切割将花费 12，因为剩余木棍的长度是 14 - 2 = 12。最后一次切割将花费 9，因为剩余棍子的长度为 12 - 3 = 4 + 5 = 9。总成本为 15 + 14 + 12 + 9 = 50。

但是，如果我们以更好的顺序进行切割，例如先切割长度 9，然后再切割长度 4 和 5。或者，如果我们在第一次切割时切割长度 8，在第二次切割中得到长度 3 + 5，我们可以发现切割所有5零件的最小成本是33。

设计一个算法来找到最低价格。

这个问题类似于问题：Optimally cut a stick at specified locations

但请注意，订单坚持对我来说并不重要。

该算法应该适用于相当高的值n，例如500000. 因此，任何枚举所有子集的解决方案对我来说都是不利的。

我想到的第一件事是将输入分成两个总和大致相同的子集。但我相信这是 NP 难题，而且我不确定它是否能让我找到这个问题的最佳解决方案。

标签： arraysalgorithmdynamic-programmingcomplexity-theory

我没有证据证明这是最优的，但我怀疑它是最优的。

put your sticks into a priority queue
while len(queue) > 1:
    take 2 smallest sticks out of queue
    merge them (record the cost)
    put the merged stick back in the queue

在您的示例中，它提出了 combine 1, 2。然后结合(1,2), 3。然后结合4, 5。然后合并(4,5), (1,2,3)为 33 的总成本。将其反转，我们在8then 4then 11then处削减9。

更新：@greybeard 评论说这看起来像 Huffman，我认识到这很简单，我不小心在这里实现了 Huffman 编码，所以这个解决方案是正确的。:-)

现在我需要阅读霍夫曼编码最适合刷新我的记忆的证据......

arrays - 切割一根棍子，使成本最小化

问题描述

解决方案

推荐阅读