简单平衡问题的简单算法

Question

我有三个桶。它们所含的水不相同，每升可达50升。

现在我想给水桶加更多水。这个数额可能会不时变化，也可能超过50x3升。我的目标是用新的水装满水桶，这样每个水桶的水量都差不多--尽可能接近相等，但这不是一个标准。也不超过50的上限。

有没有一种简单易懂的算法来平衡(尽可能多的)水桶中的水量？

• 我总是知道每个水桶里已经有多少水了。
• ，我总是知道我得到了多少新水。水桶里的
• 水是不能碰的，
• 等水位不是一个标准，但是离极限更远的是理想的

Answer 1

是的，有一个简单的算法如下：

1. 按水量对水桶进行排序。让我们称它们为none-decreasing.
2. The排序的a, b, c，平衡它们所需的总水量是(c - b) + (c - a) = 2*c - b - a。让我们称所需水量为t.
3. If，可用水小于t，不可能平衡buckets.
4. Otherwise，将c - b添加到b，c - a添加到a.

基于编辑：中新的违禁品的更新

如果您有足够的水来将较少装满的水桶中的水量提升到更满的水桶的水平，那么前面的算法工作得很好。

但是，如果没有足够的水使三者相等(请注意，这可以预先计算，如上面所述)，首先用最小的水量将桶装满，直到它等于中间的水为止。然后将剩余的可用水分成两桶，并将其平均分配给两个水桶，这两个桶水相等，但水比另一个桶少。

直觉是这样的:当你把最小的水桶加到中间的时候，你就减少了每升3乘2之间的绝对差。这是因为最小的正在接近中间和最大的一个。

示例：

a, b, c = 5, 3, 1
available_water = 4
difference = (5 - 3) + (5 - 1) + (3 - 1) = 8

add 2 to the smallest:
a, b, c = 5, 3, 3
available_water = 2
difference = (5 - 3) + (5 - 3) + (3 - 3) = 4
Note that we reduced the difference by 2 times the amount of used water

add 1 to each of the smaller buckets:
a, b, c = 5, 4, 4
available_water = 0
difference = (5 - 4) + (5 - 4) = 2

Now if we didn't follow this algorithm and just arbitrary used the water:

add 2 to the middle bucket:
a, b, c = 5, 5, 1
available_water = 2
difference = (5 - 5) + (5 - 1) + (5 - 1) = 8

add 2 to the smallest one:
a, b, c = 5, 5, 3
available_water = 0
difference = (5 - 5) + (5 - 3) + (5 - 3) = 4