算法兩套其資金匹配

我在尋找一種算法可以採取兩套整數（正面和負面的），並且發現在每個具有相同的總和整數子集內找到的子集。算法兩套其資金匹配

的問題是相似，只是在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

算法兩套其資金匹配

回答

相關問題