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

Question

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

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

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

子集:{2,1,1,3}, {4}, {4,3}, {3,2}, {1,2}, {3} 最小和=7.

备选答案:{2,1,1} {3,4} {4} {3,2} {1,2} {3} 最小和=7。

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

Answer 1

一种可能的方法是二分查找答案。

我们需要一个过程来检查我们是否可以仅使用等于或小于参数 S 的总和来划分集合。我们将此过程称为 onlySumsBelow(S)。

我们可以使用贪婪的解决方案来实现onlySumsBelow(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;
}

一旦我们有了 onlySumsBelow(S) 过程，我们就可以对答案进行二分搜索，从左端的一个区间开始，该区间的值确保搜索到的答案不低于 ( 例如 0)并且在右端有足够大的数字确保搜索到的答案不在上面(例如序列中所有数字的总和)。例如 p>

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

备注:问题末尾没有注释(限制我们考虑输入中相邻位置出现的数字子集)问题是 NP 完全问题，因为它是 Partition problem 的概括, 仅使用两组。