算法两套其资金匹配

我在寻找一种算法可以采取两套整数（正面和负面的），并且发现在每个具有相同的总和整数子集内找到的子集。算法两套其资金匹配

的问题是相似，只是在subset sum problem我正在寻找双方的子集。

下面是一个例子：

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

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

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

有谁知道是否有这种问题的现有算法？

到目前为止，我唯一的解决方案是尝试每种组合的尝试，但它在指数时间内执行，我必须对要考虑的元素数量进行硬性限制，以避免其占用过多长。

唯一的其他解决方案，我能想到的是运行在两个列表阶乘，寻找平等存在但仍然不是很有效，成倍延长的名单得到更大的重视。

来源

2009-01-14 theburningmonk

嗨burningmonk。回应刚刚删除的问题：http://iancooper.brinkster.net/Frontpage.aspx是伦敦.NET用户组。它是Google老兄的第一个结果！ – Nobody 2010-08-08 21:32:49

什么其他人说的是真的：

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

来源

2009-01-14 17:38:45

我认为可能有一个错误在这里。如果我用@ a = qw（4 5 10）和@ b = qw（14 15）运行此代码，则输出为sum（4 10）= sum（14），但如果我只是切换@b的顺序， @ b = qw（15 14）则没有输出。数组是否需要排序？还是有其他问题？ – itzy 2011-06-22 17:26:37

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

来源

2009-01-14 16:47:59

也许你想提及减少：如果A和B是你的这个问题的集合，采取通常的子集合中的工会（-B），你正在寻找总和0. – 2009-01-14 17:13:34

像子集和问题一样，这个问题是弱的 NP-complete，所以它有一个运行在时间多项式（M）中的解决方案，其中M是出现在问题实例中的所有数字的总和。你可以通过动态编程来实现。对于每个集合，您可以通过填充二维二元表来生成所有可能的总和，其中（k，m）处的“真”意味着可以通过从集合的前k个元素中选择一些元素来实现子集总和m。（k-1，m）设置为“true”（显然，如果可以从k-1个元素中获取m，则可以将（k，m）设置为“true”如果（k-1，md）被设置为“true”，其中d是集合中第k个元素的值（选择第k个元素的情况下， th元素）。

填写的表格让你在最后一列（代表全组的）所有可能的总和。对这两套做这件事，找到共同的总和。您可以通过反转您用来填充表格的过程来回溯表示解决方案的实际子集。

来源

2009-01-14 17:02:23

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

动态规划解决方案与我们现在所拥有的穷举方案没有什么不同，我猜如果我们需要最优解决方案，我们需要考虑每种可能的组合，但是生成这些穷举列表所需的时间是太长.. 做了一个快速测试，它需要以生成元素的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-15 15:22:17 theburningmonk

算法两套其资金匹配

回答

相关问题