基本算法证明

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。

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

- Yippie-Ki-Yay

---

我想知道这个是否适合发布在http://math.stackexchange.com/上，只是这么说。 - Marc Gravell

在这个例子中，我假设 K = 4 是已知的，你只是忘记提到它了，我的理解是否正确？ - flight

@quasiverse 是的，没错。 - Yippie-Ki-Yay

@hamstergene 这个例子是针对 K = 4 的，我已经更新了问题。 - Yippie-Ki-Yay

当物品的总数n不能被K整除时，情况变得有趣起来。使用您的数据并设置K == 3，您的最佳排列是[130, 160]，[170, 190, 205]，[225, 225, 260]。当n mod k != 0时，算法会变得非常混乱。 - Jim Mischel

这有点含糊不清。我不确定你是想要在所有桶中最小化最大差异的总和，还是最小化最大桶的差异。这两种定义是有区别的，因为第一种定义可以牺牲一个桶的大小来减小其他几个桶的差异。我认为你是指的第二种定义，但第一种更有趣！:-) - Codie CodeMonkey

Answer 1

假设你的数字数量总是能被K整除（不是4个一组的13个数字），那么这是正确的。

通过排序，你会尽可能让最相似的数字靠近对方，显然。问题是，如果将数字移动以使最差的值与更接近的值放在一起，是否会使最大差异变小？

答案是否定的。排序后，数字左侧的值只有相等或更低，将向左移动的数字将被较低的值包围。造成最大差异的两个数字中，至少一个会得到更糟糕的匹配，这意味着你的最大距离会变得更高。对于右侧的更高数字也同样适用。

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]

但实际上这与交换是相同的结果。

所以这就是在有两个集合时的工作原理。

有三个集合时：

[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，所以你总是会使它更糟。 最高距离highest-highM现在是highest-x，其中x<highM。

反过来也一样。如果有下一组，highM可以与更接近highest的更高数字交换，但这将使highM与更高的数字配对，从而造成更大的差异。

因此，是的，将数据排序，然后将其分成相等的部分始终会给出最小的最大差异，因为更改排序集始终会产生更糟糕的结果。

注意：如果数字不能被K整除，则情况会变得更加复杂，您必须找出最差的集合并查看是否可以将其最高或最低数字移动到下一个或前一个集合，而不会使另一个集合成为更糟的差异。 可以交换低数字与高数字的规则被取消了，因为可以用无数字交换它们，因此证明这些内容需要更高级别的技巧。

- Aberrant

Answer 2

如果初始序列已排序，则相邻数字必须具有最小差异。此外，序列开头和结尾的元素必须具有最大差异。因此，包括最后一个元素和第一个元素的任何“切割”都不能成为解决方案的一部分，因为它包含了不是最小的差异。因此，必须通过从开始处将数字序列分成均匀的部分来进行拆分。我认为你的方法是正确的，但我无法想到更正式的证明。

- Cratylus

Answer 3

自然地，通过排序可以得到数字对之间的最小差异。您可以通过简单地拆分排序后的数字来获得具有最小差异的集合。

在某些情况下，您可以在集合之间切换数字，而不会增加每个集合的最大值，因此可能有多种将数字分成集合的方法，从而给出相同的最大差异。但是，您不能在集合之间切换数字以减少任一集合的最大值而不增加另一集合的最大值。

例如，如果您有集合1,3,4,5和6,7,8,10，则可以将5和6交换位置，而不会增加任何一组中的最大差异。

如果您想要最小的平均差异，那么您可以牺牲一个集合中的最大差异，以减少另一个集合中的差异。

- Guffa

---

当然，在您的示例中，最大值增加了切换时的最大差异：在切换之前，最大差异为10-6=4，在切换之后，它将变为10-5=5。 - flolo

@flolo：是的，你说得对。我考虑的是集合中最接近的数字之间的差异，而不是集合中最小和最大数字之间的差异。 - Guffa