多个数字顺序递减的快速算法，直到总和极限

Question

我有：

包含浮

• 点字段result的dc对象的有序列表。
• limitresult总和的值。
• pack(不是更好的名字(是一个递减的值。

问题：

• 我需要按顺序减少每个dc的results，直到所有results的总和小于或等于limit(不分配低于 0result值(。

经过一些分析，我得到了以下代码：

while(self.sum > self.limit):
for dc in self.dc:
if dc.result > 0:
# max() too slow here
result = (
dc.result - self.pack
if dc.result - self.pack > 0
else 0
)
# Prevent sum() count for all list on each iteration
self.sum -= dc.result - result
dc.result = result
if self.sum <= self.limit:
break

但是对于较小的self.pack值，它的性能较低(代码执行了太多迭代(。

有没有办法使这种方法更快？

Answer 1

如果你不太关心你从包中删除了多少，只要它确保它小于总和，那么你就可以将 DC 实现为最大堆(优先级队列(，并每次弹出它，直到总和<= self.limit。这将大大加快处理时间，尤其是在大数据集中。

编辑： 由于 dc 是一个有序列表，只需将其视为堆栈并从后面弹出并从包装中取出(因为"最重"的东西在后面(。