Znaleźć dobre dopasowanie dwóch list liczb

Question

Mam dwa zestawy liczb, z SET2 posiadanie więcej przedmiotów w nim zwykle. Gwarantowane jest, że liczba: SET2 jest równa lub większa od liczby SET1. Zasadniczo, ponieważ porządek ma znaczenie, dane wejściowe są raczej listami niż zestawami.

Moim celem jest połączenie (podsumowanie)/zmienić kolejność numerów z SET2 zrobić to tak podobna do SET1, jak to możliwe. Definiuję podobieństwo jako sumę odchyleń w każdej pozycji. Zobacz this post dla sposobu obliczyć podobieństwo. Im mniejsza suma, tym lepiej.

Moim pierwszym podejściem było wypróbowanie wszystkich kombinacji i wybranie najlepszego. Działa to tylko w przypadku bardzo małych zestawów (szczególnie drugiego). Zobacz this post i odpowiedź od Rawlinga. Czy istnieje lepszy sposób na uzyskanie dobrego połączenia? Zdecydowanie nie potrzebuję tego najlepszego. Dobry wynik byłby w porządku. Oczywiście zestawy z pustymi podzbiorami są nonsensem. Niezwykle niezrównoważone zestawy nie wydają mi się zbyt obiecujące. SET1 ma zwykle około 8, ale może mieć do 18 wpisów. SET2 ma często liczbę większą niż 10 (do 35). Suma liczb w dwóch zestawach jest równa (z wyjątkiem błędów zaokrąglania).

Oto przykład z dobrych i złych wyników (nie wszystkie możliwe nich):

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) 

Proszę dać mi znać, jeśli zapomniałem opisać przesłanki czy mój opis jest niejasny lub nawet uszkodzony. Cieszę się, że mogę podać kolejny przykład.

Z góry dziękuję!

Answer 1

heurystyczne, które powinny działać całkiem dobrze:

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.} 

To będzie działać jak: iterację zestaw2 od najwyższego do najniższego, uzyskać rzeczywiste najwyższego elementu z zestaw1, zmniejszać go elementu dostał od zestaw2 i dodać ten element od set2 do elementu z wyników set1.

Należy pamiętać, aby sprawdzić, czy wszystkie elementy z zestawu 1 nie mają pustego wyniku.

Przykład 1: Set1 = {20, 9, 7, 3}, Set2 = {7, 6, 6, 4, 2, 2, 2, 2, 2, 2, 2, 2}.

iter1: fromSet2 = 7, Set1 = {20:{}, 9:{}, 7:{}, 3:{}}, fromSet1=20. Zmniejszenie 20 o 7 i dodanie 7 do wyniku. Zaktualizowano: Set1 = {13:{7}, 9:{}, 7:{}, 3:{}}.

iter2: fromSet2 = 6, Set1 = {13:{7}, 9:{}, 7:{}, 3:{}}, fromSet1=13. Zmniejszenie 13 o 6 i dodanie 6 do wyniku. Zaktualizowano: Set1 = {7:{7, 6}, 9:{}, 7:{}, 3:{}}.

iter3: fromSet2 = 6, Set1 = {7:{7, 6}, 9:{}, 7:{}, 3:{}}, fromSet1=9. Zmniejszenie 9 o 6 i dodanie 6 do wyniku. Zaktualizowano: Set1 = {7:{7, 6}, 3:{6}, 7:{}, 3:{}}.

iter4: fromSet2 = 4, Set1 = {7:{7, 6}, 3:{6}, 7:{}, 3:{}}, fromSet1=7. Zmniejszenie 7 na 4 i dodanie 4 do wyniku. Zaktualizowano: Set1 = {3:{7, 6, 4}, 3:{6}, 7:{}, 3:{}}.

iter5: fromSet2 = 2, Set1 = {3:{7, 6, 4}, 3:{6}, 7:{}, 3:{}}, fromSet1=7. Zmniejszenie 7 o 2 i dodanie 2 do wyniku. Zaktualizowano: Set1 = {3:{7, 6, 4}, 3:{6}, 5:{2}, 3:{}}.

...