等和子集混合

Question

问题如下：

给定一组正整数 { a1 , a2 , a3 , ... , an }，其中没有相同的数字（ a1 只存在一次，a2 只存在一次，...）例如A = {12 , 5 ,7 ,91 }。 问题： A 是否有两个不相交的子集 A1 = { b1,b2,...,bm } 和 A2 = { c1,c2,...,ck} 使得 b1+b2+...+bm = c1+ c2+...+ck ？

请注意以下事项： A1 和 A2 不一定要覆盖 A，因此问题不会自动简化为子集和问题。 例如 A = {2,5,3,4,8,12} A1= {2,5} 所以 A1 之和为 7 A2= {3,4} 所以 A2 之和为 7 我们发现 A 的两个不相交子集具有所描述的属性，因此问题得到解决。

我怎么解决这个问题？ 我能做一些比找到所有可能的（不相交）子集、计算它们的总和并找到两个相等的总和更好的事情吗？

感谢您的时间。

Answer 1

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

我不确定你的意思是 B 和 C 没有义务覆盖 A，所以问题不会自动简化为子集和问题。 请检查SUBSET-SUM的定义。

Answer 2

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

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

量子电子器件。

---

说真的，您可以进行的一项优化（假设我们正在讨论正数）是仅检查小于或等于 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
}

Answer 3

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

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

Answer 4

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

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