将一组2n个整数划分为n个整数的两个子集,其总和为正

给定一组2n个整数,是否可以在n个整数的两个子集中找到一个分区,每个子集的总和为正 .

我的想法:我们表示集合v [1],...,v [2n]的值 . 如果存在该组的前j个整数的分区分别为k和jk整数的两个子集,则设S [j,k,s1,s2] = 1,使得第一子集总和为s1,第二子集求和到s2 . (s1和s2当然可以是否定的)

我们有以下关系:S [j 1,k,s1,s2] = 1 iff S [j,k-1,s1-v [j 1],s2] = 1或S [j,k,s1,s2 -v [j 1]] . 原因是你必须添加* j 1 th " element to either the " first " subset or the " second“ .

如果s1_0> 0且s2_0> 0使得S [2n,n,s1_0,s2_0] = 1,则问题的答案为是 .

你怎么看?有没有更好的方法(在时间/空间复杂性方面)?我从一开始就假设这是一个动态编程问题,还有其他方法吗?

回答(1)

2 years ago

不是动态编程,但仍然是一个想法 .

let A and B be two empty sets

sort v
for i in [0, 2, ..., 2n)
    // note that v[i] <= v[i + 1]
    assign v[i] to the set with the largest sum
    assign v[i + 1] to the set with the smallest sum

return sum(A) >= 0 and sum(B) >= 0

我们的想法是尽可能均匀地分配数字,并限制负数造成的损害,同时保持集合的基数相同

  • 当两组都有负数时,数字被分配,使得它们的总和尽可能减少

  • 当正好一组具有正总和时,最大数字将被分配给具有负和的集合

  • 当两组都有正数时,任何作业都没有问题