Gegeben zwei Listen von Zahlen und eine Liste von Summen (keine in einer bestimmten Reihenfolge):
%Vor% Wie finde ich alle Mengen von Paaren d wo d[k] = (a[i], b[j]) so dass c[k] = a[i] + b[j] wo Paare von a und b ohne Ersatz verwendet werden? (Alle Listen können Duplikate haben)
Für c = [7,7,7] :
(1 Antwort, weil alle Permutationen im Wesentlichen äquivalent sind)
Ich möchte das mit Listen der Länge ~ 500 machen, so dass eine naive Suche nach Übereinstimmung / Zurückverfolgung nicht in Frage kommt.
Okay, da ist der Brute-Force-Ansatz mit dem Beschneiden. Dies benötigt O (N ^ 3)
Zur Erleichterung der Demonstration gehe ich durch ein N-mal-N-Quadrat, das die Summe von a und b
hat %Vor% Und ich suche c = {6,7,8}
zu bauen
Ich finde eine 6 in S . Ich entferne es und markiere seine Zeile und Spalte als nicht verfügbar
Dann versuche ich eine '7'
zu finden %Vor%Und schließlich die '6'
%Vor%Die erste Schleife (die für '6') wird fortgesetzt und findet ein weiteres Spiel: (2,4). Dies wird dann die zweite Lösung bilden {(2,4) (1,6) (3,5)}
Nun, eine Möglichkeit, dies zu verbessern, ist eine dynamische Programmierung: Finde alle möglichen Kombinationen heraus, die das Ergebnis vorher ergeben.
%Vor%Und nun wird derselbe Algorithmus mit gegebenen Heuristiken in O (S_l1 * S_l2 * ... S_lN) laufen, wobei S_li die Länge von S_i bezeichnet.
Dieser kann im Durchschnitt einen Faktor schneller ausführen. Es behandelt auch den c = {7,7,7} Fall richtig.
Das ist so ziemlich alles, was ich habe.
Tags und Links algorithm matching subset-sum