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

如何将整数数组划分为N个子集，使得这些子集的总和最小？例如，该数组由11个元素组成，我需要6个子集。如何将数组分成N个最小和子集？

{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。

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

来源

2016-05-23 Arijit Pramanick

我不明白你的意思最小的总和。在第一行中有一组总和为3. – Carlos

将数组划分为N个子集，使得每个子集的总和小于或等于每个子集可能的最小总和。 –

尝试制作6个分区，其中每个分区的总和将小于7. –

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

我们需要一个程序来检查我们是否可以仅使用等于或低于参数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）和在右端有足够大的数字以确保搜索到的答案不在上面（，例如是序列中所有数字的总和）。

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

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

来源

2016-05-23 14:23:05 qwertyman

如何通过过程onlySumsBelow（S）添加数字时如何保持分区数量？ –

我为onlySumsBelow（S）过程添加了一些伪代码。另外，提到如果效率不是问题，您可以避免二分查找并使用线性搜索。 – qwertyman

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

回答

相关问题