7

The problem is the following:

You are given a set of positive integers { a1 , a2 , a3 , ... , an } in which there are no same numbers ( a1 exists only once ,a2 exists only once,...) eg A = {12 , 5 ,7 ,91 }. Question: Are there two disjoint subsets of A , A1 = { b1,b2,...,bm } and A2 = { c1,c2,...,ck} so that b1+b2+...+bm = c1+c2+...+ck ?

Note the following: It is not obligatory for A1 and A2 to cover A, so the problem isn't automatically reduced to the subset sum problem. eg A = {2,5,3,4,8,12} A1= {2,5} so sum of A1 is 7 A2= {3,4} so sum of A2 is 7 We found two disjoint subsets of A with the described property so the problem is solved.

How can I solve this problem? Can I do something better than find all possible (disjoint)subsets, calculate their sums and find two equal sums?

Thank you for your time.

4

4 回答 4

3

没问题，这里有一个O(1)解决方案。

A1 = {}; 
A2 = {};
sum(A1) == sum(A2) /* == 0 */

QED。

说真的，您可以进行的一项优化（假设我们谈论的是正数）是只检查小于或等于sum(A)/2.

对于其中的每个元素，A都有三个选项可以使它O(3^N)：

  1. 把它放进去A1
  2. 把它放进去A2
  3. 丢弃它

这是 Perl 中的一个幼稚解决方案（计算匹配项，如果您只想测试存在性，则可以提前返回）。

use List::Util qw/sum/;

my $max = sum(@ARGV)/2;
my $first = shift(@ARGV); # make sure we don't find the empty set (all joking aside) and that we don't cover same solution twice (since elements are unique)
my $found = find($first,0, @ARGV);
print "Number of matches: $found\n";

sub find {
    my ($a, $b, @tail) = @_;
    my $ret = $a == $b? 1 : 0; # are a and b equal sub-sets?
    return $ret unless @tail;

    my $x = shift @tail;
    $ret += find($a + $x, $b, @tail) if $a + $x <= $max; # put x in a
    $ret += find($a, $b + $x, @tail) if $b + $x <= $max; # put x in b
    return $ret + find($a, $b, @tail); # discard x
}
于 2009-02-08T12:49:46.713 回答
2

如果答案是否定的，那么所有 n 个数字的总和至少为 2^n-1。因此，如果 n 很大，并且数字是 32 位整数，那么答案几乎总是肯定的。如果 n 很小，您可能可以蛮力。

最困难的情况可能是当 n 约为 30 时。

于 2009-02-08T13:11:28.153 回答
1

我认为您可以像子集和问题一样解决它。取布尔函数 Q(i,s)，如果 a0,a1,...,ai 有一个总和为 s 并包含 ai 的子集，则该函数为真。您可以使用动态编程为所有 i 和 s 计算它（这是标准方法）。然后，您可以扫描 Q 的所有值以查找在其关联行中具有多个真值的 s。

如果存在这样的 s，则意味着您找到了两个具有相同总和的不同子集。它们可能不是不相交的，但是您可以从每个集合中删除公共元素并获得两个总和相等的不相交集合。不过，其中一个可能是空的。

于 2009-02-08T20:49:05.570 回答
0

这个问题似乎至少和 SUBSET-SUM 一样难。如果我们可以找到 A 的两个子集：B = {b1,...,bp} 和 C = {c1,...,cq} 使得 b1+...+bp = -c1-...-cq，或者如果我们确定不存在，那么我们已经解决了 SUBSET-SUM(A)（忽略 0 ∈ A 的平凡情况）。

我不确定您的意思是 B 和 C 没有义务覆盖 A，因此问题不会自动归结为子集和问题。请检查 SUBSET-SUM 的定义。

于 2009-02-10T05:09:23.910 回答