将数组划分为具有最小差异的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]]