最大化集合中元素之间的最小差异
Maximizing the minimum difference between elements in a set
最近想到了这个问题，想到了"instinctive"贪心的解法但是无法证明其最优性
给你 N 个整数，V1, V 2, ..., VN 和 K 集 (K < N).
你需要找到一种方法将整数划分到集合中，使同一集合中任意两个元素之间的最小差异最大化。
例如，当整数为 1、5、6、8、8 并且您有 2 个集合时，划分整数的最佳方式是
{1, 6, 8}
{5, 8}
所以最小差在6和8之间，也就是2
这个排列不是唯一的，例如
{1, 5, 8}
{6, 8}
也给出最小差值 2。
我在想，如果我可以用一个贪心算法来解决这个问题
我会先排序，然后把所有V1,V1 +K, V1+2K...一起，然后都是 V2,V2+K,V2+2K...一起，依此类推。
是否有此解决方案最优性的证明，或此解决方案不起作用的反例？
谢谢。
是的，这是最佳的。我们将证明，如果使用您的过程出现差异 D，那么对于数字的任何排列，同一组中的一对数字最多相差 D。
为了证明这一点，考虑将排序后的数字一个一个地添加到K组中。我们称排序后的数字为 x[i]。假设我们将 x[n] 添加到其中一个集合中。该集合中的最大值是 x[n-k]，对于某些 D.
，x[n]-x[n-k] = D
现在，集合 x[n-k], x[n-k+1], ..., x[n] 是一组 k+1 个数，它们最多相差D（对于 x[n]-x[n-k] = D）。
根据鸽巢原理，这k+1个数无论怎么排列都必须在同一个集合中，所以最大最小距离最多为D。
这就证明如果你的过程中出现一个距离D，那么最大最小距离最多可以达到D。
让 D_min 成为使用您的过程的同一组中两个数字之间的最小差异。然后我们证明了可实现的最大最小距离 <= D_min，而且 D_min <= 最大最小距离（因为 D_min 是最小距离）这表明 D_min 是最大最小距离。
最近想到了这个问题，想到了"instinctive"贪心的解法但是无法证明其最优性
给你 N 个整数，V1, V 2, ..., VN 和 K 集 (K < N).
你需要找到一种方法将整数划分到集合中，使同一集合中任意两个元素之间的最小差异最大化。
例如，当整数为 1、5、6、8、8 并且您有 2 个集合时，划分整数的最佳方式是
{1, 6, 8}
{5, 8}
所以最小差在6和8之间，也就是2
这个排列不是唯一的，例如
{1, 5, 8}
{6, 8}
也给出最小差值 2。
我在想，如果我可以用一个贪心算法来解决这个问题
我会先排序，然后把所有V1,V1 +K, V1+2K...一起，然后都是 V2,V2+K,V2+2K...一起，依此类推。
是否有此解决方案最优性的证明，或此解决方案不起作用的反例？
谢谢。
是的，这是最佳的。我们将证明，如果使用您的过程出现差异 D，那么对于数字的任何排列，同一组中的一对数字最多相差 D。
为了证明这一点，考虑将排序后的数字一个一个地添加到K组中。我们称排序后的数字为 x[i]。假设我们将 x[n] 添加到其中一个集合中。该集合中的最大值是 x[n-k]，对于某些 D.
，x[n]-x[n-k] = D现在，集合 x[n-k], x[n-k+1], ..., x[n] 是一组 k+1 个数，它们最多相差D（对于 x[n]-x[n-k] = D）。
根据鸽巢原理，这k+1个数无论怎么排列都必须在同一个集合中，所以最大最小距离最多为D。
这就证明如果你的过程中出现一个距离D，那么最大最小距离最多可以达到D。
让 D_min 成为使用您的过程的同一组中两个数字之间的最小差异。然后我们证明了可实现的最大最小距离 <= D_min，而且 D_min <= 最大最小距离（因为 D_min 是最小距离）这表明 D_min 是最大最小距离。