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

Question

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

问题类似于subset sum problem除了我正在寻找两侧的子集。

这是一个例子:

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

列表 B {21, 7, -4, 180}

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

有谁知道是否有解决此类问题的现有算法？

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

我能想到的唯一其他解决方案是在两个列表上运行阶乘并在其中寻找相等性，但这仍然不是很有效，并且随着列表变大，所需时间呈指数级增长。

Answer 1

别人说的是真的:

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 正确地指出这个解决方案是错误的，更糟糕​​的是，在多个方面!!我对此感到非常抱歉，我希望在上面的新代码中解决这些问题。尽管如此，仍然存在一个问题，即对于任何特定的子集和，它只打印可能的解决方案之一。与之前的直接错误问题不同，我将其归类为故意限制。祝你好运并提防错误!