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

其他人说的是真的:

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是问题实例中出现的所有数字的总和。你可以通过动态编程来实现这一点。对于每个集合,您可以通过填充一个二维二进制表来生成所有可能的和,其中(k,m)处的“true”表示可以通过从集合的前k个元素中选取一些元素来实现子集和m。

你迭代地填充它——如果(k-1,m)设置为“真”(很明显,如果你能从k-1个元素中得到m,你可以通过不选择第k个元素从k个元素中获得m),或者如果(k-1,m-d)设置为”真“,其中d是集合中第k个元素的值(选择第k元素的情况),则将(k,m)设为”真”。

填写表格可以得到最后一列(代表整个集合的列)中所有可能的总和。对两个集合都这样做,并找到共同的总和。您可以通过颠倒填写表格的过程来回溯表示解决方案的实际子集。

非常感谢所有的快速回复!

动态规划解决方案与我们现在的穷举方法并没有什么不同,我想如果我们需要最优解决方案,我们确实需要考虑每种可能的组合,但生成这个穷举的总和列表所需的时间太长了。。 做了一个快速测试,快速生成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

对于我们试图解决的业务问题来说,这是不可接受的。。我要回到绘图板上,看看我们是否真的需要知道所有的解决方案,或者我们可以只使用一个(最小/最大的子集,例如)来代替,希望这能帮助简单地解决问题,并使我的算法达到预期的效果。

还是谢谢你!

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