通过最少的移动次数来最小化装满球的桶的最大重量的算法
Algorithms to Minimize Maximum Weight across Buckets filled with Balls by Making Least Number of Moves
我有 K 个桶。每个桶包含一定数量的球 B，其中每个球都有一定的重量。
我想知道是否有算法可以完成以下任务：
我想一次移动一个，并以一种最小化所有桶中包含的最大重量的方式将一些重量从一个桶重新定位到另一个桶。我想重复这个过程，直到我通过最少的步骤实现了 Weights in Buckets 的最平衡配置。
在解决这个问题时是否有有用的算法？
以下是我想到的方法：
天真：遍历桶中球的所有组合，并采用具有 min(max(所有桶的重量) 的变体。这是我的最佳配置。现在一次移动一个球直到你实现了这个配置。这会工作，但不可能编程，因为我们有 num_buckets^num_balls 复杂性，这在球数量很大时效率低下。
Greedy Tree：从头开始，贪婪地以循环方式将球分配到各个箱子中。在每次迭代中 - 将球放入具有最小最大值的容器中。这不会提供最佳平衡，但会提供更好的平衡，然后我可以一步一步来实现此配置。
这感觉像是一个问题，我有一个成本函数，第一步有 BxK 步移动。
是否有已知的算法可以启发更好的解决方案？ （装箱在这里不起作用，因为我有固定数量的箱子。）我不是在寻找解决方案，而是寻找解决平衡问题的算法，即使不完全相同，看起来也与此类似。
首先，让我们稍微限制一下贪心算法：将球按降序排列，最重的在前。
之后，按照从最重到最轻的顺序处理垃圾箱。对于每个箱子，寻找一个交换或移动，以减少其重量而不会使移动的另一个箱子达到最大重量。继续此过程，直到无法再改进最重的垃圾箱。
我无法证明这是否会为您提供最佳解决方案，但它会非常好。 :-)
我有 K 个桶。每个桶包含一定数量的球 B，其中每个球都有一定的重量。
我想知道是否有算法可以完成以下任务：
我想一次移动一个，并以一种最小化所有桶中包含的最大重量的方式将一些重量从一个桶重新定位到另一个桶。我想重复这个过程，直到我通过最少的步骤实现了 Weights in Buckets 的最平衡配置。
在解决这个问题时是否有有用的算法？
以下是我想到的方法：
天真：遍历桶中球的所有组合，并采用具有 min(max(所有桶的重量) 的变体。这是我的最佳配置。现在一次移动一个球直到你实现了这个配置。这会工作，但不可能编程，因为我们有 num_buckets^num_balls 复杂性，这在球数量很大时效率低下。
Greedy Tree：从头开始，贪婪地以循环方式将球分配到各个箱子中。在每次迭代中 - 将球放入具有最小最大值的容器中。这不会提供最佳平衡，但会提供更好的平衡，然后我可以一步一步来实现此配置。
这感觉像是一个问题，我有一个成本函数，第一步有 BxK 步移动。
是否有已知的算法可以启发更好的解决方案？ （装箱在这里不起作用，因为我有固定数量的箱子。）我不是在寻找解决方案，而是寻找解决平衡问题的算法，即使不完全相同，看起来也与此类似。
首先，让我们稍微限制一下贪心算法：将球按降序排列，最重的在前。
之后，按照从最重到最轻的顺序处理垃圾箱。对于每个箱子，寻找一个交换或移动，以减少其重量而不会使移动的另一个箱子达到最大重量。继续此过程，直到无法再改进最重的垃圾箱。
我无法证明这是否会为您提供最佳解决方案，但它会非常好。 :-)