找到兩個數字列表的好匹配

Question

我得到了兩組數字，其中SET2通常有更多的項目。確保SET2的計數等於或大於SET1的計數。 Acutally，因爲順序重要的輸入是列表而不是集合。

我的目標是（總結）從SET2結合/重新排序的數字，使其類似於SET1越好。我將相似性定義爲每個位置偏差的總和。有關我計算相似度的方式，請參閱this post。總和越小越好。

我的第一種方法是嘗試所有組合並挑選最好的組合。這隻適用於很小的集合（尤其是第二集）。見this post和Rawling的答案。 有沒有更好的組合方式？我絕對不需要最好的一個。一個好的結果會很好。很明顯，空子集的集合是無稽之談。極端不平衡的集合對我來說似乎不是很有希望。 SET1往往有8個左右，但最多可以有18個條目。 SET2的計數通常超過10（最多35）。 兩組數字之和相等（舍入誤差除外）。

這是好的和壞的結果的例子（不是所有可能的）：

SET1 = { 272370, 194560, 233430 }; SET2 = { 53407.13, 100000, 365634.03, 181319.07 } 

     272370   |  194560   |  233430 
--------------------------------------------------------------------- 
    365634.03   | 100000 + 53407.13 |  181319.07  (best match) 
    365634.03   |  181319.07  | 100000 + 53407.13 (good) 
    365634.03   |  100000   |181319.07 + 53407.13 (ok) 
     53407.13   |365634.03 + 100000 |  181319.07  (bad) 
     53407.13   |365634.03 + 181319.07 |  100000  (bad) 
.     |365634.03 + 181319.07 | 53407.13 + 100000 (invalid) 
53407.13 + 100000 |365634.03 + 181319.07 |      (invalid) 

請讓我知道如果我忘了描述一個前提或我的描述不清，甚至錯誤的。我也很樂意提供另一個例子。

在此先感謝！

Answer 1

啓發式，這應該工作相當不錯：

1. list<int> set1, set2; 
2. sort(set2) // decreasing, set2[0] would be the greatest value in set2 
3. struct set1item = {set1index, value, list<int> chosen} 
4. prepare list<set1item> set1items from set1 //(index = index in set1 list, value = set1[index] and chosen = null) 
5. put set1items to some priorityqueue pq // ordered by value 
6. for each set2item in set2{ 
7.  item = pq.first() 
8.  item.chosen.add(set2item); 
9.  item.value -= set2item; 
10. pq.updateFirst(item) 
11.} 

它的工作，如：遍歷SET2從最高到最低，從設置1得到實際的最高元素，通過元素減少從SET2了，並添加該元素從set2到set1結果中的元素。

您必須記得檢查set1中的所有元素是否沒有空結果。

例1： Set1 = {20, 9, 7, 3}, Set2 = {7, 6, 6, 4, 2, 2, 2, 2, 2, 2, 2, 2}。

iter1：​​，Set1 = {20:{}, 9:{}, 7:{}, 3:{}}，fromSet1=20。 將20減去7並將其結果加7。更新：Set1 = {13:{7}, 9:{}, 7:{}, 3:{}}。

iter2：fromSet2 = 6，Set1 = {13:{7}, 9:{}, 7:{}, 3:{}}，fromSet1=13。 將13減6並將其結果加6。更新：Set1 = {7:{7, 6}, 9:{}, 7:{}, 3:{}}。

iter3：fromSet2 = 6，Set1 = {7:{7, 6}, 9:{}, 7:{}, 3:{}}，fromSet1=9。 將9減6並將其結果加6。更新：Set1 = {7:{7, 6}, 3:{6}, 7:{}, 3:{}}。

iter4：fromSet2 = 4，Set1 = {7:{7, 6}, 3:{6}, 7:{}, 3:{}}，fromSet1=7。 將7減4並將其結果加4。更新：Set1 = {3:{7, 6, 4}, 3:{6}, 7:{}, 3:{}}。

iter5：fromSet2 = 2，Set1 = {3:{7, 6, 4}, 3:{6}, 7:{}, 3:{}}，fromSet1=7。 將7減2並將其結果加2。更新：Set1 = {3:{7, 6, 4}, 3:{6}, 5:{2}, 3:{}}。

...