算法問題：最佳匹配子集

我正在構建一個匹配交易的程序。以下是我目前面臨的問題的解讀。我需要一些關於算法的幫助。算法問題：最佳匹配子集

給定兩組具有相似屬性（交易日期，賬戶，符號）的交易A和B，我需要在A和B內找到交易a的子集，其中sum（a）最接近總和（b）。這裏sum（）是該子集的特定屬性（淨錢）的總和。需要最接近的匹配的原因是，如果我們沒有得到完美的匹配（理想情況），我們希望下一個最接近的匹配。注意：sum（a）可以大於或小於sum（b）。

我明顯想要做到這一點，而不使用強制方法來生成A和B的所有組合並進行比較。

我覺得這可以用一些動態編程方法來完成，但我無法提出任何具體的東西。將不勝感激任何幫助。

來源

2011-03-21 user668661

符號的最知名的樣品確實大快建設：來讓a.netMoney只是'了'。因此，給定A = {a，e，i}和B = {b，c}，蠻力不僅僅是尋找（abs（a - b），abs（a - c） b），...abs（i-c）），但是（X-Y）的左邊可以是A的單個元素的每個和，即：（（a + e）-b）...也是？ – 2011-03-21 02:11:23

是的。那就對了。 – user668661 2011-03-21 02:27:29

這個問題是NP-hard。

該證明是從子集和減少，這是已知是NP難。給定子集和的任何實例，其中我們被賦予一組S元素進行求和，並且給出一個目標數k，我們可以通過讓A成爲集合S並讓B成爲單一集合{k}來構造你的問題的一個實例。。如果我們解決你的問題，並發現最接近的匹配不完全是k，那麼我們知道無法總結S的一個子集來獲得k。否則，如果有一種方法可以將S的元素總和爲k，那麼匹配將完全等於k，並且我們知道某個子集確實加起來了目標。

因爲這個問題是NP難的，所以你不應該期待一個能夠在多項式時間運行的解決方案，或者它比蠻力更好。我想你需要稍微放鬆一下，以獲得好的結果。

來源

2011-03-21 02:21:24 templatetypedef

它會幫助我建立一定的寬容度，並找到屬於該範圍內的所有子集而不是簡單的最佳匹配？ – user668661 2011-03-21 02:30:51

這可能會有所幫助，但請記住，有多個指數級的子集可以查看，並且任何列出多個子集的算法如果產生太多的輸出結果都會遇到麻煩。不知道更多關於這個問題的信息，我不知道我還能提供多少幫助......你能詳細談談你想要做什麼嗎？ – templatetypedef 2011-03-21 02:32:15

哎喲，這聽起來像是類固醇subset-sum。對於你的問題規模（A和B的元素數量）有一個想法是很好的。問題肯定會是NP難題，因此您可能無法使用如下所示的精確解決方案。

一個簡單的DP解決方案是爲每個可能的總和值分別求解A和B的子集和。因此，如果每個集合最多有10個元素可以在0到50之間，那麼對於A和B，使用DP來回答0到500之間的X的問題「是否有一個子集與X和？」。然後只是看看他們有哪些共同點，或者找出A中某個可能總和到B中某個可能總和的最小距離。

（注意：我說'簡單'，不是'高效'！但是由於NP硬度等原因，沒有解決方案以大於O的速度大大快於此）

來源

2011-03-21 02:27:02 usul

因此，對於強力算法，我們構建A和B的超集，並構建所有的組合他們，總結他們，建立絕對的總和，並找到最低？

sa = superset (A) //() (a) (e) (i) (a, e), (a, i) (e, i) (a, e, i) 
sb = superset (B) 

sas = supersetAsums // 0, a, e, i, a+e, a+i, e+i, a+e+i 
sbs = supersetAsums 

ssas = sorted (sas) 
ssbs = sorted (sbs)

現在，你可以通過兩個列表循環，如果SSAS（I）<辦學團體（J）你增加Ĵ，否則增量我，看的ABS（DIFF）是否比當前分鐘（ABS（差異較小））。

這裏的問題是子集，它得到N. :)

來源

2011-03-21 02:27:50

算法問題：最佳匹配子集

回答

相關問題