简单平衡问题的简单算法

Question

我有三个桶。它们所含的水量不同，每个可以最多容纳 50 升。

现在我想往水桶里加更多的水。此数量可能会不时变化，也可能超过 50 x 3 升。我的目标是用新水装满水桶，使每个水桶中的水量大约相等 - 尽可能接近相等，但这不是标准。而且也没有超过上限50

是否有一种简单易读的算法可以平衡（尽可能多地）水桶中的水量？

我总是知道每个桶里已经有多少水。
我总是知道我得到了多少新水。
桶里的水不能碰
等水位不是标准，但离限制越远越好

Answer 1

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

按水量对水桶进行排序。我们称它们为 a, b, c 排序 none-递减。
平衡它们所需的总水量为 (c - b) + (c - a) = 2*c - b - a。让我们调用所需的数量 t.
如果可用水少于t，则无法平衡水桶。
否则，将 c - b 添加到 b 并将 c - a 添加到 a。

根据编辑中的新约束进行更新：

如果您有足够的水使装得较少的水桶中的水量达到装得较多的水桶中的水量，则之前的算法就可以正常工作。

但如果没有足够的水使三者都相等（请注意，这可以如上所述预先计算），首先用最小量的水填充桶，直到等于中间一个。然后将剩余的可用水量平均分配给水量相等但水量比对方少的两个水桶。

直觉是这样的：当您添加到最小的桶直到到达中间的桶时，每增加一升，您就会将三者之间的绝对差值减少 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

简单平衡问题的简单算法

Simple algorithm for a simple balancing problem

algorithm

load-balancing

pseudocode