在两个总和匹配的整数中查找子集的算法

Question

我正在寻找一种算法,它可以采用两组整数(正数和负数),并找到每个具有相同总和的子集.

问题类似于子集求和问题,除了我正在寻找两侧的子集.

这是一个例子:

列表A {4,5,9,10,1}

清单B {21,7,-4,180}

所以这里唯一的匹配是:{10,1,4,9} <=> {21,7,-4}

有谁知道这种问题是否存在现有的算法？

到目前为止,我所拥有的唯一解决方案是蛮力方法,它尝试每个组合,但它在指数时间内执行,我不得不对要考虑的元素数量设置硬限制,以避免花费太长时间.

我能想到的唯一其他解决方案是在两个列表上运行一个阶乘并寻找那里的等式,但这仍然不是很有效,并且随着列表变大而需要指数地增长.

Answer 1

像子集求和问题一样,这个问题是NP完全弱的,因此它有一个以时间多项式(M)运行的解,其中M是问题实例中出现的所有数字的总和.您可以通过动态编程实现这一目标.对于每个集合,您可以通过填充二维二进制表来生成所有可能的总和,其中(k,m)处的"真"表示可以通过从集合的前k个元素中挑选一些元素来实现子集和m.

你迭代地填充它 - 如果(k-1,m)设置为"true",你将(k,m)设置为"true"(显然,如果你可以从k-1元素得到m,你可以从k得到它通过不选择第k个元素或if(k-1,md)被设置为"true",其中d是集合中第k个元素的值(选择第k个元素的情况).

填充表格可以获得最后一列中的所有可能总和(表示整个集合的总和).对两个集合执行此操作并查找公共总和.您可以通过反转用于填充表的过程来回溯表示解决方案的实际子集.

Answer 2

别人说的是真的:

1. 这个问题是NP完全的.简单的减少是通常的子集和.只有当A联合(-B)的非空子集总和为零时,才能通过注意A的子集与B的子集(不是两者都是)来表示这一点.

2. 这个问题只是NP完全弱,因为它是所涉及数字大小的多项式,但推测它们的对数是指数的.这意味着问题比"NP-complete"的绰号更容易.

3. 你应该使用动态编程.

那么我对这次讨论的贡献是什么？好吧,代码(在Perl中):

@a = qw(4 5 9 10 1);
@b = qw(21 7 -4 180);
%a = sums( @a );
%b = sums( @b );
for $m ( keys %a ) {
    next unless exists $b{$m};
    next if $m == 0 and (@{$a{0}} == 0 or @{$b{0}} == 0);
    print "sum(@{$a{$m}}) = sum(@{$b{$m}})\n";
}

sub sums {
    my( @a ) = @_;
    my( $a, %a, %b );
    %a = ( 0 => [] );
    while( @a ) {
        %b = %a;
        $a = shift @a;
        for my $m ( keys %a ) {
            $b{$m+$a} = [@{$a{$m}},$a];
        }
    %a = %b;
    }
    return %a;
}

它打印

sum(4 5 9 10) = sum(21 7)
sum(4 9 10 1) = sum(21 7 -4)

所以,值得注意的是,有多个解决方案适用于您的原始问题!

编辑:用户itzy正确地指出这个解决方案是错误的,更糟糕​​的是,在多种方式!! 我很抱歉,我希望在上面的新代码中解决这些问题.尽管如此,仍然存在一个问题,即对于任何特定的子集和,它只打印一种可能的解决方案.与之前出现的直接错误问题不同,我将其归类为故意限制.祝你好运并提防虫子!