algorithm - 基本算法证明

Question

我有一个数字序列，例如:170, 205, 225, 190, 260, 130, 225, 160 我必须将它们分成具有固定数量元素的集合，以便集合元素之间的最大差异被最小化。

我可以保证，如果我需要将元素拆分为 K 元素集，则元素的全局数量等于 Z * K。

对于 K = 4 的示例，可以这样执行最佳拆分:

(1) : 130 160 170 190 (最大差值等于 60)

(2) : 205 225 225 260 (最大差值等于 55)

因此，这种情况下的全局最大差异等于 60。

---

现在，问题是:我是否假设我可以简单地排序初始数据并从头开始将其分成偶数部分？如果这是正确的，我如何证明它？如果不是，我应该使用哪种方法来解决这个问题？

Answer 1

假设您的数字总能被 K 整除(因此不是 13 个数字以 4 个为一组)，这是正确的。

显然，通过排序，您可以获得彼此尽可能接近的最相似数字。问题是，如果将数字移动到具有更接近值的集合中最差的值，这是否会使最大差异变小？

答案是否定的。排序时，数字左侧的唯一值等于或小于，将向左移动的数字将被较低的值包围。在造成最大差异的两个数字中，至少有一个会得到一个更差的伙伴，这意味着你的最大距离会变得更高。它的工作方式与右边的较大数字相同。

Sorted:
[lowest, low, low, x] distance1 = x-lowest
[y, high, high, highest] distance2 = highest-y

Swapped:
[lowest, low, low, y] distance3 = y-lowest
[x, high, high, highest] distance4 = highest-x

因为 x < y(假设它们不相等，因为交换毫无意义)，distance3 > distance1 和 distance4 > distance2，这意味着事情变得更糟。

如果您在此处放置更高的值，它的工作方式相同。

无论一个数字有多离谱，在该位置放置另一个数字都会使它们更离谱。

另一种选择是将整个子集向左移动一个空格:

[lowest, low, low, y]
[high, high, highest, x]

但这实际上和交换的结果是一样的。

这就是 2 组的工作原理。

三组:

[lowest, low, low, x]
[lowM, lowM, highM, highM]
[highM, y, high, highest]

交换 x 和 y 与之前相同。即使 x 非常接近甚至等于左下角的高点(如果中间的低点和高点实际上相等)，y 仍然高于 x，使得最低点的差异更大，并且 x 离最高点更远。

向前移动一堆数字:

[lowest, low, lowM, lowM]
[highM, highM, highM, y]
[x, highM, high, highest];

也许最大的区别是 highM 和 highest 之间的距离，现在这个距离被移除了。但是，由于您只能通过在此处放置更低的值来将其从最高位置移开，因此您总是使情况变得更糟。最高距离 highest-highM 现在是 highest-x，并且 x < highM。

反之亦然。如果有下一组，highM 可以与更接近最高的数字交换，但这会使 highM 具有更高的数字，从而导致更大的差异。

所以是的，对数据进行排序然后将其分成相等的部分总能得到最小的最大差异，因为更改排序的集合总是会得到更差的结果。

注意:如果数字不能被 K 整除，它会变得更复杂，你必须找出最差的一组，看看你是否可以将其最高或最低的数字移动到下一组或上一组而不做另一组设置更差的差异。您只能将低数与高数交换的规则已被删除，因为您可以将它们与无数交换，因此证明这一点是一个全新的水平。