削减成本，使成本最小化
你必须把一根长度为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 cutting a stick at specified locations
但请注意，顺序对我来说并不重要。
该算法应该适用于相当高的n，如500000。所以，任何枚举所有子集的解决方案对我来说都是不好的。
我想到的第一件事是将输入分成两个大致相同和的子集。但我相信这是一个NP难题，我不确定它是否会让我找到这个问题的最优解决方案。
回答 2
Stack Overflow用户
发布于 2019-11-23 07:40:51
我没有证据证明这是最优的，但我怀疑它是最优的。
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在您的示例中，出现了组合1, 2。然后结合(1,2), 3。然后结合4, 5。然后组合(4,5), (1,2,3)，总成本为33。颠倒过来，我们依次在8、4、11和9处切分。
更新：@greybeard的评论说这看起来像Huffman，我意识到这是微不足道的，我无意中在这里实现了Huffman编码，所以这个解决方案是正确的。:-)
现在我需要阅读霍夫曼编码最能唤醒我记忆的证据……
Stack Overflow用户
发布于 2019-11-23 12:32:13
我认为你应该把下次削减的成本降到最低。要做到这一点，一个好方法是更快地处理较大的部分。因此，首先我们可以使用总的切割大小，然后删除更大的部分。
def get_min_costs_sorted(stick, pieces):
if len(pieces) == 1:
return 0
piece = pieces[0]
print("Cutting {} into {}-{}".format(stick, piece, stick - piece))
return stick + get_min_costs_sorted(stick - piece, pieces[1:])
def get_min_costs(stick, pieces):
pieces.sort(reverse=True)
total = sum(pieces)
if stick > total:
print("Cutting {} into {}-{}".format(stick, total, stick - total))
return stick + get_min_costs_sorted(total, pieces)
else: # no cutting
return get_min_costs_sorted(total, pieces)https://stackoverflow.com/questions/59001659
复制相似问题
腾讯云开发者
