等同于子集混合
等同于子集混合
提问于 2019-06-19 01:25:58
问题如下：
给你一组正整数{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的两个不相交的子集描述的属性，所以问题解决了。
我怎么解决这个问题？我能做的比找到所有可能的（不相交的）子集更好，计算它们的总和并找到两个相等的总和吗？
感谢您的时间。
Stack Overflow用户
发布于 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
}
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/-100001254
复制相关文章
相似问题