vector<int> p1,p2;
vector<int> result1,result2;
vector<int> array={12,323,432,4,55,223,45,67,332,78,334,23,5,98,34,67,4,3,86,99,78,1};
void partition(unsigned int i,long &diffsofar, long sum1,long sum2)
{
if(i==array.size())
{
long diff= abs(sum1 - sum2);
if(diffsofar > diff)
{
result1 = p1;
result2 = p2;
diffsofar = diff;
}
return;
}
p1.push_back(array[i]);
partition(i+1,diffsofar,sum1+array[i],sum2);
p1.pop_back();
p2.push_back(array[i]);
partition(i+1,diffsofar,sum1,sum2+array[i]);
p2.pop_back();
return;
}
我最近也遇到了同样的问题,并发布了一个相关问题(这里是:0/1背包问题)。不同之处在于,如果原始集合有偶数个元素,则结果子集必须具有相同的大小。为了确保这一点,我在@Sandesh Kobal的答案中添加了几行代码。
void partition(unsigned int i,long &diffsofar, long sum1,long sum2)
{
int maxsize = (array.size()+1)/2;
if(p1.size()>maxsize)
return;
if(p2.size()>maxsize)
return;
if(i==array.size())
{
...
partition
之后,我添加了if(diffsofar==0) return;
。如果我们已经找到了最优解,继续搜索就没有意义了...我看到的所有文章都采用动态编程方法。我们真的需要吗?
假设给定的数组是arr
使用以下算法:
a = []
和b = []
sum_a = sum_b = 0
for x in arr:
if sum_a > sum_b:
b.append(x)
sum_b += x
else:
a.append(x)
sum_a += x
sum_a
和sum_b
之间的绝对差将是两个子集之间可能的最小差。
考虑arr = [3,1,1,2,2,1]
排序数组:arr = [3,2,2,1,1,1]
a = [], b = []
a = [3], b = []
a = [3], b = [2]
a = [3], b = [2,2]
a = [3,1], b = [2,2]
a = [3,1,1], b = [2,2]
a = [3,1,1], b = [2,2,1]
sa = 5, sb = 5
最小差值: 5 - 5 = 0