最有效的方法是平均填写不同大小的“水桶”的未排序列表

Question

假设我有一个bucket的未排序列表。(每个桶都有一个size属性。)假设我有一个数量Q，必须尽可能均匀地分布在桶的列表中(即最小化最大值)。

如果水桶是按增大的大小排序的，那么解决方案是显而易见的:完全填充每个桶，比如buckets[i]，直到Q/(buckets.length-i) <= buckets[i]->size，然后用相同数量的Q/(buckets.length-i)填充剩余的桶，如图中所示：

​

​

，如果桶没有排序的话，最有效的解决方法是什么？

我只能想到这样的迭代(伪代码)：

while Q > 0
    for i in 0..buckets.length-1
        q = Q/(buckets.length-i)
        if q > buckets[i]->size
            q = buckets[i]->size
        buckets[i]->fill(q)
        Q -= q

但我不确定是否有更好的方法，或者对列表进行排序是否更有效。

(我面临的实际问题更多，例如，这个“未排序”列表实际上是由一个单独的属性“秩”排序的，该属性确定当数量不均匀分配时，哪些桶将得到额外的填充，等等。因此，例如，为了使用排序-然后填充方法，我会根据桶大小和级别对列表进行排序。但是知道这个问题的答案会帮助我找出其他的。)

Answer 1

在第一步中，从n个有限容量的未排序桶开始，k个无限桶(存储k，而不是这些桶的列表，在第一次迭代k=0时)和一定量的水w，在O(n)时间，我们将问题简化为n'，k'，w‘的另一个实例，其中n’

在所有n个有限容量中，选择中间值(即选择一个，使一半的容量更高，一半更低)。这可以在O(n)时间内完成(选择算法)。计算1)低容量和2)中位容量乘以容量较高的桶数(包括无限容量)的总和。

如果小于w，您知道需要将水桶填充得更高，所以特别是所有容量较低的水桶都将被填满。移除它们，将它们的容量之和从w中移除，您就完成了这个迭代，n'=n/2。

另一方面，如果和大于w，你知道没有桶将填充到中位容量或更高。因此，所有容量较高的桶都可以被移除，并将其数量添加到无限大桶的数量中。W保持不变。再次，n'=n/2，我们完成了。

跳过了一些简单的细节(特别是如何处理许多桶容量完全相同的情况)来保持简短。当你知道正确的水位后，你也需要在最后进行一些清理，为每个“无限”(即非满)桶设置它。

Answer 2

在许多情况下，如果对数据进行排序，解决方案是“如此简单”或“非常有效”，但如果不是，则非常复杂或无效，最好的解决方案通常是先对数据进行排序，然后再采用简单有效的解决方案。尽管这意味着您将有首先排序数据的开销，但是有许多非常好的排序算法可用于几乎任何目的，而且在许多情况下，“首先对数据进行排序，然后对其应用简单有效的算法”的总开销仍然低于“不对数据进行排序，并对其应用非常复杂、无效的算法”的总开销。

您需要按不同键排序的数据对我来说只意味着，这里需要两个列表，每个列表按照不同的标准排序。除非我们在这里讨论几千个桶，否则第二个列表的内存开销很可能不是问题(毕竟这两个列表都只包含指向桶对象的指针，这意味着每个指针有4/8个字节，这取决于您是否有32位或64位代码)。一个列表有按大小排序的桶，另一个列表有按“级别”排序的桶，当添加问题中描述的新项时，您使用“按大小排序的列表”，而使用“排序按级别”列表的方式与现在使用它的方式相同。

Answer 3

我认为在线性时间内这是可能的，但是我被困在了某个点上。也许你能解决这个问题，也许它不能这样解决。

考虑以下算法。

在二进制搜索的基础上，我们想要找到最小的桶，但没有完全填满。在一个桶的列表中找到这样一个桶可能在线性时间内是可能的，但正如我所说，我被困在这里了。一旦我们找到了那个桶，剩下的就变得微不足道了，因为对于所有较小的桶，我们总结它们的大小，从要放置的项目总数中减去它，除以我们刚刚找到的桶的数量。

下面是解决这个问题的一个尝试:什么是没有完全装满的最小的桶？该算法是由QuickSelect驱动的。

挑一个枢轴桶。看看它是不是比我们正在寻找的桶更小或更大。(这一步微不足道。)

• 如果它较小，将小于或等于这个桶的所有桶的大小相加，从项目总数中减去这个和，然后继续搜索包含所有较大桶的集合。
• 如果它更大，我们将不得不做一件类似的事情，但是现在减去放置在所有桶中的比这个大的物品的数量。我们不知道要放在这些桶里的物品的数量。这就是问题所在..。但是如果我们知道的话，我们会继续搜索包含所有小桶的集合。

如果该算法有效，它将在预期的线性时间内运行随机枢轴元素(参见QuickSelect)。