数量分配算法性能

Question

我有一个场景，我将以一个类似的例子来帮助更好地理解。

有N个已知容量不同的桶。我们有M球，我们需要将它们放入这些桶中，以完全或部分地填充它们。现有算法的工作原理如下：

对于每个桶计算分数effect = (Bi + 1)/Ci，其中Bi和Ci分别是桶中的当前球数和ith桶的容量。识别出效果最低的水桶，并从M中取出一个球，重复上面的过程，直到没有剩下的球(M=0)，或者所有的桶都装满了。

上面的算法产生了所需的输出，但是当有大量的桶和许多球要分配时，它会出现性能问题。内环必须运行M * N来分配所有的球。

我试着优化它，把大容量的球分配给每个桶。新办法如下：

对于每个水桶，执行以下操作:计算差异(否)。Di = Ci - Bi )。算出数字。在Mi = (Di * M)/S中，S是所有水桶的差和(D1+D2....Dn)。

虽然速度快得多，但结果与以前的方法不一样，特别是在没有足够的球填满所有桶的情况下。(即M< S)

有人能建议一种几乎独立于M的算法，并产生与最初一次分配一个球的方法相同的输出吗？

Answer 1

只有当你把球放进桶里时，你才能通过重新计算来优化。这意味着不是M*N，而是M+N计算。

当然，这意味着您需要内存来存储计算。一桶一桶。

您还可以通过将它们保持在优先级队列中来优化查找效果最低的桶。