如何将数组划分为N个最小和子集？

Question

如何将整数数组划分为N个子集，使这些子集的和最小？

例如，数组由11个元素组成，我需要其中的6个子集。

{2,1,1,3,4,4,3,2,1,2,3}

子集：＜code＞｛2，1，1，3｝，｛4｝，｝4，3｝，｝3，2｝，1，2｝，｛3｝＜/code＞最小和＝7。

另一个答案是：{2,1,1}{3,4}{4}{3,2}{1,2}{3}最小和=7。

注意:在分区时，必须保持数字在原始集合中出现的顺序。

Answer 1

一种可能的方法是二进制搜索答案。

我们需要一个过程来检查我们是否可以仅使用等于或小于参数< code>S的和来划分集合。让我们把这个过程称为< code > onlysumsblow(S)。

我们可以使用贪婪的解决方案来实现< code > onlysumsblow(S)。总是在每个子集中添加尽可能多的元素，并在达到大于S的和之前停止(我在这里假设我们没有负元素，这可能会使讨论复杂化)。如果我们不能使用允许的子集数到达序列的末尾，那么和是无效的(太小)。

function onlySumsBelow(S) {
    partitionsUsed = 1;
    currentSum = 0;

    for each value in sequence {
        if (value > S) return false;

        if (currentSum + value > S) {
            // start a new partition
            currentSum = value;  
            partitionsUsed++;   
        } else {
            currentSum += value;
        }
    }

    return partitionsUsed <= N;
}

一旦我们有了唯一的SumsBelow（S）过程，我们就可以对答案进行二叉搜索，从一个间隔开始，该间隔在左端有一个值，确保搜索的答案不低于（例如0），在右端有一个足够大的数字，以确保搜索的答案不在上方（例如，序列中所有数字的总和）。

如果效率不是一个问题，而不是二进制搜索，你可以简单地尝试多个候选答案一个接一个，从一个足够小的值开始，例如所有数字的总和除以N，然后增加一个，直到达到一个精细的解决方案。

备注：问题末尾没有注释（这限制了我们考虑出现在输入中相邻位置的数字子集），这个问题是NP完全的，因为它是分区问题的推广，它只使用两个集合。