我有三個桶。它們不含相同數量的水，每個最多可容納 50 升。
現在我想往桶里加更多的水。這個數量可能會不時變化，也可能超過 50 x 3 升。我的目標是用新水裝滿水桶，使每個水桶中的水量大致相等 - 盡可能接近相等，但這不是標準。并且不超過50的上限。
是否有一種簡單易讀的演算法可以平衡（盡可能多地）水桶中的水量？
- 我總是知道每個桶里已經有多少水。
- 我總是知道我得到了多少新水。
- 已經裝在桶里的水不能碰
- 等水位不是標準，但最好遠離限制
uj5u.com熱心網友回復：
是的，有一個簡單的演算法如下：
- 按水量對水桶進行分類。讓我們稱它們
a, b, c為非遞減排序的。 - 你需要平衡它們的總水量是
(c - b) (c - a) = 2*c - b - a。讓我們呼叫所需的數量t。 - 如果可用水小于
t，則無法平衡水桶。 - 否則，添加
c - btob和c - atoa。
根據編輯中的新約束進行更新：
如果您有足夠的水將裝得較少的水桶中的水量增加到裝得較多的水桶的水位，那么前面的演算法就可以正常作業。
但如果沒有足夠的水使三個都相等（請注意，這可以如上所述預先計算），首先用最少量的水填充桶，直到它等于中間的水。然后分配剩余的可用水量，并將其平均分配到兩個相同但水量比另一個少的水桶之間。
直覺是這樣的：當您添加到最小的桶直到到達中間的桶時，每增加一升，您將三者之間的絕對差減少 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
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/409370.html
標籤：
上一篇：最速下降并找到最佳步長