通过最少的移动次数来最小化装满球的桶的最大重量的算法

Question

我有 K 个桶。每个桶包含一定数量的球 B，其中每个球都有一定的重量。

我想知道是否有算法可以完成以下任务:

我想一次移动一个，并以最小化所有桶中包含的最大重量的方式将一些重量从一个桶重新定位到另一个桶。我想重复这个过程，直到我通过最少的步骤实现了 Weights in Buckets 的最平衡配置。

在解决这个问题时，是否有可供引用的算法？

以下是我想到的方法:

1. 天真:遍历桶中球的所有组合，并采用具有 min(max(所有桶的重量) 的变体。这是我的最佳配置。现在一次移动一个球，直到你达到这种配置。这可行，但无法编程，因为我们有 num_buckets^num_balls 的复杂性，如果球的数量很大，效率会很低。

2. Greedy Tree:从头开始，贪婪地以循环方式将球分配到各个容器中。在每次迭代中 - 将球放入具有最小最大值的容器中。这不会提供最佳平衡，但会提供更好的平衡，然后我可以一步一步来实现此配置。

这感觉像是一个问题，我有一个成本函数，并且在我的第一步有 BxK 步数。

是否有已知算法可以启发更好的解决方案？ (装箱在这里不起作用，因为我有固定数量的箱子。)我不是在寻找解决方案，而是寻找解决平衡问题的算法，即使不完全相同，看起来也与此类似。

Answer 1

首先，让我们稍微限制一下贪心算法:将球按降序排列，最重的放在最前面。

之后，从最重的到最轻的处理垃圾箱。对于每个箱子，寻找一个交换或移动，以减少其重量而不会使移动的另一个箱子达到最大重量。继续此过程，直到无法再改进最重的垃圾箱。

我无法证明这是否会为您提供最佳解决方案，但它会非常好。 :-)