平等之子集混合动力 [英] Equal sum subsets hybrid

问题描述

问题如下：

正在给定的一组正整数{A1，A2，A3，...，一个}在其中没有相同的数字（A1仅存在一次，A2仅存在一次，...）例如的甲= { 12，5，7，91}。 问：是否存在A的两个不相交的子集，A1 = {B1，B2，...，BM}和A2 = {C1，C2，...，CK}使B1 + B2 + ... + BM = C1 + C2 + ... + CK？

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 ?

请注意以下几点：这不是强制性的A1和A2来覆盖，所以这个问题不会自动降低到子集和问题。 例如：A = {2,5,3,4,8,12} A1 = {2,5}使A1的总和为7 A2 = {3,4}所以A2的总和为7 我们发现了两个不相交的子集所描述的属性，这样问题就解决了​​。

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?

感谢您的时间。

推荐答案

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

No problem, here's an O(1) solution.

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

QED。

---

说真的，一是优化可以使（假设我们谈论的正数）是只检查子集小于或等于总和（A）/ 2 。

Seriously, one optimization you can make (assuming that we're talking about positive numbers) is to only check sub-sets less or equal to sum(A)/2.

有关中的每个元素 A 有三个选项，这使得它 0（3 ^ N）：

For every element in A there are three options which makes it O(3^N):

1. 放入 A1
2. 放入 A2
3. 丢弃它

1. Put it in A1
2. Put it in A2
3. Discard it

下面是Perl中的一个天真的解决方案（计数的比赛中，你可以有一个早期的回报，如果你只是想测试的存在）。

Here's a naive solution in Perl (that counts the matches, you can have an early return if you just want to test existence).

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
}

这篇关于平等之子集混合动力的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！