将数组划分为差异最小的 k 个分区子数组

Question

我有一个问题：给定一个数组 a1。aN 一个非负 K，(K<N)。将数组划分为差异最小的 K 分区子阵列。之后，列出找到的优化子阵列。 例如： 输入：a=[1,2,3,4,7], K=3输出：{1,4}, {2,3}, {7}解释：1+4=5, 2+3=5, 7=7=> 差异=2 是最小 => 选择

Answer 1

您所说的问题的最佳解决方案是NP-hard，但这里有一个简单的幼稚方法，在许多情况下都相当有效：

def naive_partition(a, k):
result = [[] for _ in range(k)]
sums = [0] * k
for x in sorted(a, reverse=True):
i = sums.index(min(sums))
sums[i] += x
result[i].append(x)
return result

print(naive_partition([1, 2, 3, 4, 7], 3))

结果：

[[7], [4, 1], [3, 2]]