如何平衡兩個數組之間的差異如何最小化？

我有一個數組A[]={3,2,5,11,17}和B[]={2,3,6}，B的大小總是大於A.少現在，我必須從每一個元件B映射到這樣的不同元素的總差sum(abs(Bi-Aj))變爲最小（凡畢已被映射到AJ）。算法的類型是什麼？如何平衡兩個數組之間的差異如何最小化？

對於示例輸入，我可以選擇2->2=0，3->3=0然後6->5=1。所以總成本是0 + 0 + 1 = 1。我一直在考慮對這兩個數組進行排序，然後從A中得到第一個sizeof B元素。請問這是否工作？

來源

2013-10-29 Tamim Addari

嘗試自己的想法在A = {1,2,3,4}'和'B = {3,4}'上看看它是否有效。 – molbdnilo

不，它不起作用.. :(我該怎麼辦？我有另外一個想法，把A與B元素排列在一起，然後嘗試匹配元素，但是在我的問題中，A可能高達200，B高達50給出1.38036910e + 112個百分點，這是不可行的。我如何解決它？ –

這可能是一個更難的問題。糾正我，如果我錯了，但你不能解決子集和只使用O（n）這個問題的實例？使B只包含零，並測試每個可能的子集大小（它們的''n'）總差是否爲零（O（n）以獲得該總差）因此，如果你可以在一些多項式時間M中做到這一點，那麼你可以解決SubsetSum in O（M * n^2） – harold

它可以被認爲是不平衡的Assignment Problem。

成本矩陣應該是B [i]和A [j]的差值。您可以將虛擬元素添加到B中，以便問題變得平衡並使成本相關性非常高。

然後Hungarian Algorithm可以用來解決它。

對於示例情況下的[] = {3,2,5,11,17}和B [] = {2,3,6}的成本矩陣應爲：

. 3 2 5 11 17 
2 1 0 3 9 15 
3 0 1 2 8 14 
6 3 4 1 5 11 
d1 16 16 16 16 16 
d2 16 16 16 16 16

來源

2013-10-29 09:43:11

匈牙利語算法太複雜，我不明白，你能給一個有用的鏈接？ –

這個鏈接以簡單的步驟解釋算法。 http://www.wikihow.com/Use-the-Hungarian-Algorithm –

如何做第5步？用盡可能少的線覆蓋零元素。（如果行數等於行數，則轉到步驟9） –

如何平衡兩個數組之間的差異如何最小化？

回答

相關問題