11

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

这个问题类似于子集和问题，除了我在两边都寻找子集。

这是一个例子：

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

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

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

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

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

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

4

4 回答 4

9

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

您迭代地填充它 - 如果 (k-1,m) 设置为“true”，则将 (k,m) 设置为“true”（显然，如果您可以从 k-1 个元素中获取 m，则可以从 k 中获取它通过不选择第 k 个元素）或者如果 (k-1,md) 设置为“true”，其中 d 是集合中第 k 个元素的值（在您选择第 k 个元素的情况下）。

填写表格可以获得最后一列中所有可能的总和（代表整个集合的总和）。对两组都这样做并找到共同的和。您可以通过反转用于填充表格的过程来回溯表示解决方案的实际子集。

于 2009-01-14T17:02:23.500 回答
9

其他人说的是真的：

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

于 2009-01-14T17:38:45.003 回答
1

非常感谢所有快速回复！

动态规划解决方案与我们现在拥有的详尽方法并没有真正的不同，我想如果我们需要最佳解决方案，我们确实需要考虑每一种可能的组合，但是生成这个详尽的总和列表所花费的时间太长了..做了一个快速测试，为 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

对于我们试图解决的业务问题，这不是真的可以接受的。我要回到绘图板上，看看我们是否确实需要知道所有的解决方案，或者我们可以只用一个（最小的/最大的子集，例如）相反，希望这可以帮助解决问题并使我的算法按预期执行。

一样的谢谢！

于 2009-01-15T15:22:17.913 回答
0

子集总和是 Np 完全的，你可以多项式地将你的问题简化为它，所以你的问题也是 NP 完全的。

于 2009-01-14T16:47:59.503 回答