算法找到在两个整数集，其款项匹配的子集 [英] Algorithm to find subset within two sets of integers whose sums match

问题描述

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

I'm looking for an algorithm which can take two sets of integers (both positive and negative) and find subsets within each that have the same sum.

现在的问题是类似子集和问题的不同之处在于我在寻找子集在两侧。

The problem is similar to the subset sum problem except that I'm looking for subsets on both sides.

下面是一个例子：

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

List A {4, 5, 9, 10, 1}

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

List B {21, 7, -4, 180}

因此​​，这里唯一的比赛是： {10，1，4,9}＆其中; => {21，7，-4}

So the only match here is: {10, 1, 4, 9} <=> {21, 7, -4}

有谁知道是否有现有的算法，这个有点问题呢？

Does anyone know if there are existing algorithms for this kinda problems?

到目前为止，唯一的解决办法我已经是一个强​​力的办法，尝试各种组合，但它执行的指数时间，我已经把一个硬限制对元素的数量来考虑，以避免它花费的时间太长

So far, the only solution I have is a brute force approach which tries every combination but it performs in Exponential time and I've had to put a hard limit on the number of elements to consider to avoid it from taking too long.

其他唯一的解决办法我能想到的是运行在两个列表阶乘，寻找平等有但仍然不是非常有效，并采取指数越长的列表变得更大。

The only other solution I can think of is to run a factorial on both lists and look for equalities there but that is still not very efficient and takes exponentially longer as the lists get bigger.

推荐答案

其他人所说的是真实的：

What others have said is true:

1. 这个问题是NP完全问题。一个简单的减少是通常的子集之和。您可以通过记录表明，该是A款项到B的一个子集（不能同时为空）仅当A联盟（-B）款项零一个非空的子集。

1. This problem is NP-complete. An easy reduction is to usual subset-sum. You can show this by noting that a subset of A sums to a subset of B (not both empty) only if a non-empty subset of A union (-B) sums to zero.

此问题是只有弱NP完全，在它的多项式中的号的所涉及的大小，但推测是指数在其的对数的。这意味着，这个问题比绰号NP完全可能意味着更容易。

This problem is only weakly NP-complete, in that it's polynomial in the size of the numbers involved, but is conjectured to be exponential in their logarithms. This means that the problem is easier than the moniker "NP-complete" might suggest.

您应该使用动态规划。

那我促成这一讨论？嗯，code（在Perl）：

So what am I contributing to this discussion? Well, code (in 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)

所以，值得注意的是，有不止一个解决方案，在您的原始问题的作品！

so, notably, there is more than one solution that works in your original problem!

修改：用户itzy正确地指出，这种解决方案是错误的，更糟的是，以多种方式！我很抱歉，我已经希望解决在新的code以上这些问题。尽管如此，仍然存在一个问题，即，对于任何特定子集总之，只打印可能的解决方案之一。不同的是previous的问题，这是直线上升的错误，我会归类这是一个有意的限制。祝您好运和提防的错误！

Edit: User itzy correctly pointed out that this solution was wrong, and worse, in multiple ways!! I'm very sorry about that and I've hopefully addressed these concerns in the new code above. Nonetheless, there is still one problem, namely that for any particular subset-sum, it only prints one of the possible solutions. Unlike the previous problems, which were straight-up errors, I would classify this as an intentional limitation. Best of luck and beware of bugs!

这篇关于算法找到在两个整数集，其款项匹配的子集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！