如何将整数数组划分为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。
注意:数字出现在原始集合中的顺序必须在分区时保留。
如何将整数数组划分为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。
注意:数字出现在原始集合中的顺序必须在分区时保留。
一种可能的方法是二进制搜索答案。
我们需要一个程序来检查我们是否可以仅使用等于或低于参数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,它只使用两组。
如何通过过程onlySumsBelow(S)添加数字时如何保持分区数量? –
我为onlySumsBelow(S)过程添加了一些伪代码。另外,提到如果效率不是问题,您可以避免二分查找并使用线性搜索。 – qwertyman
我不明白你的意思最小的总和。在第一行中有一组总和为3. – Carlos
将数组划分为N个子集,使得每个子集的总和小于或等于每个子集可能的最小总和。 –
尝试制作6个分区,其中每个分区的总和将小于7. –