将一个数组分成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 => difference=2 is min => choose

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]]

将一个数组分成k个差值最小的分区子数组

Divide an array into k partitions subarray that have minimum difference

python

arrays

optimization

partition