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

一尘不染

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

algorithm

我正在寻找一种算法，该算法可以采用两组整数（正数和负数），并在每个整数中找到具有相同总和的子集。

该问题与子集总和问题类似，除了我要在两侧寻找子集。

这是一个例子：

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

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

因此，这里唯一的匹配项是：{10，1，4，9} <=> {21，7，-4}

有谁知道是否存在针对此类问题的现有算法？

到目前为止，我唯一的解决方案是蛮力方法，它尝试每种组合，但是它在指数时间内起作用，并且我不得不对要考虑的元素数量设置硬性限制，以免花费太长时间。

我能想到的唯一的其他解决方案是在两个列表上都运行阶乘并在此处查找相等性，但这仍然不是很有效，并且随着列表变大需要花费指数的时间。

阅读 211

2020-07-28

共1个答案

一尘不染

别人说的是真的：

这个问题是NP完全的。一个简单的减少就是通常的子集和。您可以通过指出A的子集和B的子集（不都为空）来证明这一点，仅当A联合的非空子集（-B）的总和为零时。
这个问题仅是弱NP完备的，因为它是所涉及数字的多项式，但是推测其对数是指数级的。这意味着问题比“ NP-complete”这个名字所暗示的要容易。
您应该使用动态编程。

那么，我对该讨论有何贡献？好吧，代码（在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正确指出此解决方案是错误的，而且在多种方面更糟！我对此感到非常抱歉，并希望在上面的新代码中解决这些问题。尽管如此，仍然存在一个问题，即对于任何特定的子集总和，它仅显示一种可能的解决方案。与之前的问题（直接错误）不同，我将其归为故意限制。祝您好运，并提防错误！

2020-07-28