问题如下:
给你一组正整数{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的两个不相交的子集描述的属性,所以问题解决了。
我怎么解决这个问题?我能做的比找到所有可能的(不相交的)子集更好,计算它们的总和并找到两个相等的总和吗?
感谢您的时间。
发布于 2019-06-19 11:25:13
没问题,这是一个O(1)
解决方案。
A1 = {};
A2 = {};
sum(A1) == sum(A2) /* == 0 */
QED。
说真的,你可以做的一个优化(假设我们正在谈论正数)只是检查小于或等于的子集sum(A)/2
。
对于每个元素,A
有三个选项可以实现O(3^N)
:
A1
A2
这是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
}
https://stackoverflow.com/questions/-100001254
复制相似问题