我有一串数字,例如:
现在问题来了:我的假设是,我可以简单地对初始数据进行排序,并从开头开始将其拆分成相等的部分。 如果正确,我该如何证明它?如果不正确,我应该使用哪种方法来解决这个问题?
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。现在问题来了:我的假设是,我可以简单地对初始数据进行排序,并从开头开始将其拆分成相等的部分。 如果正确,我该如何证明它?如果不正确,我应该使用哪种方法来解决这个问题?
K = 4
是已知的,你只是忘记提到它了,我的理解是否正确? - flightK = 4
的,我已经更新了问题。 - Yippie-Ki-Yayn
不能被K
整除时,情况变得有趣起来。使用您的数据并设置K == 3
,您的最佳排列是[130, 160],[170, 190, 205],[225, 225, 260]
。当n mod k != 0
时,算法会变得非常混乱。 - Jim Mischel