algorithm - 平衡一组数字的最佳解决方案

Question

所以我正在为一个副项目写作并尝试优化:

给定一组 n 个数字(例如 [4, 10, 15, 25, 3])，我们想让每个数字在给定的公差范围内大致相同(即如果我们想要精确，那么它应该是 11.4在上面的例子中)。

我们可以添加/删除一个并添加到另一个。例如，我们可以从 [3] -5 和 +5 到 [1]，这会给我们 [9, 10, 10, 25, 3]。

我的限制是我们希望每个数字之间的“转移”次数最少(例如，如果我们从 [3] 执行 -3.6，那么它算作一次“转移”)。

不关心性能(我能看到的最多是一组最多 50 个数字)但真的希望将传输保持在最低限度。

我们可以假设公差从 +/- 1 开始，但可以动态改变。

Answer 1

该算法的目标是确保列表中的每个数字在给定的公差范围内大致相同。因此，如果公差为零，则所有数字必须等于列表中所有值的平均值(在整个算法中将保持不变)。考虑到公差，列表中的所有数字都必须属于包含区间 [average - 0.5*TOLERANCE, average + 0.5*TOLERANCE]。

该算法的主要迭代涉及检索最大值和最小值，并从最大值“转移”到最小值，以便值 最远 平均值(这可以是最小值或最大值)落在所需的间隔内。此过程不断迭代，直到最大值和最小值彼此之间的距离不超过 TOLERANCE 个单位。

该算法的伪代码如下所示:

target = average of the values in the list

while dist(max, min) > TOLERANCE
    x = maximum of dist(max, target) and dist(min, target)
    transfer (x - 0.5*TOLERANCE) units from maximum into minimum

dist(a, b) 可以简单地定义为 abs(a - b)

此算法平均运行时间约为 O(n^2)，需要的迭代次数略多于 n，其中 n 是值的数量。

该算法所需的迭代次数不到每次迭代中仅对最小值和最大值进行平均的朴素次优方法所需迭代次数的一半。