algorithm - 将整数数组分成 K 组，使得每组具有最小范围

Question

所以，更正式地说，我得到了 N 个数字，需要将它们分成 K 个组，这些组中没有一个是空的。每组中的范围总和需要最小。例如:

N = 4，K = 2，输入为 {5,3,1,1}。

一种可能的解决方案是 {5,3},{1,1}。范围之和为 2 ((5-3)+(1-1))。

另一种看待它的方法是 {1,1,3}{5}，它也是 2((3-1)+(单个数字的范围是 0))。

范围始终是组中最大数字与组中最小数字之间的差值。

当我在互联网上搜索时，很明显我需要使用动态规划，但我想到的只是 K=2 的解决方案。

有人可以帮忙吗？

Answer 1

1. 对数组进行排序。
2. 令a_m 为数组的第m 个元素；那么，令 a_m = a_m – a_m–1 ∀m ∈ [1; N).减法循环必须向后运行以避免改变 a_m–1。 a₀ ≡ 0.
3. 对结果数组进行排序，保持元素的初始索引按照与元素本身相同的顺序排序。
4. 获取最后的 K–1 个索引:这些索引与 0 一起是搜索组的第一个元素的索引。