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

StackOverflow https://stackoverflow.com/questions/443712

题

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

问题类似于 子集和问题 除了我正在寻找两边的子集。

这是一个例子：

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

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

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

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

到目前为止，我唯一的解决方案是一种蛮力方法，它会尝试每种组合，但它会在指数时间内执行，并且我必须对要考虑的元素数量进行严格限制，以避免花费太长时间。

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

有帮助吗？

解决方案

别人说的都是真的：

  1. 这个问题是NP完全问题。一个简单的减少是通常的子集和。您可以通过注意到仅当 A 并集 (-B) 的非空子集之和为零时，A 的子集之和为 B 的子集（并非都为空）来证明这一点。

  2. 这个问题只是弱 NP 完全问题，因为它是 数字 涉及，但据推测其影响呈指数级增长 对数. 。这意味着这个问题比“NP 完全”这个绰号所暗示的要容易。

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

其他提示

像子集和问题，这个问题是的弱 NP完全，所以它具有在时间多项式（M）运行的解决方案，其中M是出现在该问题的所有数字的总和实例。可以实现与动态规划。对于每一组可以生成通过填充一个2维二进制表，其中“真”在（K，M）表示的子集之和，m可以通过拾取从该组的第一k个元素的一些元素而实现的所有可能的和。

您填写它迭代 - 设置（K，M）为 “true” 如果（K-1，M）设置为 “真”（当然，如果你可以从K-1的元素男，你可以得到它从由不采摘第k k个元素），或者如果（K-1，MD）被设置为“真”，其中d是第k个元素的集合中的（所述值，其中你选择的第k个的情况下元件）。

灌装表让你的所有在最后一列（代表全组的一个）的可能数额。这样做对两个集合，并找到共同的款项。您可以通过颠倒您用来填充表的过程回溯代表解决方案的实际子集。

非常感谢所有的快速反应！

在动态规划解决方案是不穷尽计算策略，我们现在所拥有的真正不同，我想，如果我们需要的最佳解决方案，我们就需要考虑各种可能的组合，但所花费的时间来产生资金的这种详尽的清单太长.. 做了快速测试，它需要以产生用于元素的x个所有可能的和的时间非常快速地去在1分钟：

11 elements took - 0.015625 seconds
12 elements took - 0.015625 seconds
13 elements took - 0.046875 seconds
14 elements took - 0.109375 seconds
15 elements took - 0.171875 seconds
16 elements took - 0.359375 seconds
17 elements took - 0.765625 seconds
18 elements took - 1.609375 seconds
19 elements took - 3.40625 seconds
20 elements took - 7.15625 seconds
21 elements took - 14.96875 seconds
22 elements took - 31.40625 seconds
23 elements took - 65.875 seconds
24 elements took - 135.953125 seconds
25 elements took - 282.015625 seconds
26 elements took - 586.140625 seconds
27 elements took - 1250.421875 seconds
28 elements took - 2552.53125 seconds
29 elements took - 5264.34375 seconds

这对于我们正在努力解决的业务问题是不是真的可以接受..我要回到绘图板，看看我们是否确实需要知道所有的解决方案，或者我们可以做一个（最小/最大的子集，例如），而不是，希望可以帮助简单的问题，使我的算法进行到expectaion。

由于所有相同！

子集和是NP完全问题，您可以多项式减少你的问题，所以你的问题是NP-完成了。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top