Ich arbeite an einer Anwendung, die zwei Datensätze basierend auf verschiedenen Kriterien zusammenbringen muss, einschließlich der Summe einer beliebigen Anzahl von Elementen aus jedem Satz. Ich habe das Problem auf diese Aussage reduziert:
Geben Sie für eine Menge von Elementen und Transaktionen den kleinsten Satz von Elementen an, wobei die Summe der Summe der kleinsten Transaktionssätze entspricht. (Es gibt einige Komplexität, die ich für diesen Beitrag ignoriere, aber im Moment bin ich nur besorgt über die Gesamtbeträge, die passen, nicht um Daten, Beschreibungen, Clearing-Unterschiede usw.)
Oder, mathematisch: Wenn Sie zwei Mengen von Zahlen erhalten, finden Sie die kleinste Menge von jedem, wo die Summen gleich sind.
Die anderen ähnlichen SO-Fragen, über die ich schon gesprochen habe, gehen davon aus, dass Sie die Summe im Voraus wissen oder die Menge von jedem Satz kennen, für den Sie sich entscheiden.
Und hier ist ein Test, der (glaube ich) veranschaulicht, wofür ich hingehe.
%Vor%Ich suche nach einer eleganten Lösung, die das passieren lässt, aber jeden Pseudocode oder Vorschlag nehmen wird, der mich dorthin bringt;)
Brute-Force:
%Vor%Verwenden Sie die Subsets-Methode aus dem EvenMoreLINQ-Projekt .
Dies kann mit dynamischer Programmierung in O(nW) time gelöst werden, wobei W die Größe der größten Summe ist. Lösen Sie das Rucksackproblem für beide Sets, um ein Array für jedes zu generieren, das alle möglichen Summen enthält, und verfolgen Sie die Anzahl von Artikel verwendet. Vergleichen Sie dann die gleichen Summen in jedem Array, um das Minimum für jedes
Nicht getestet, aber das ist die Idee.
%Vor%Wenn die zwei Mengen eine gemeinsame Nummer enthalten, gibt es eine Lösung der Größe 1.
Wenn nicht, versuche alle Summen von zwei Zahlen (es gibt N-wähle-zwei oder N*(N-1)/2 in jedem Satz). Vergleichen Sie sie mit der Sammlung von Ein- und Zwei-Zahlen-Summen.
Wenn keine Freude ist, versuch alle Summen von drei Zahlen und vergleiche sie mit 1, 2 oder 3 Zahlen. und so weiter, bis alle Summen (2 ** N für eine Menge der Größe N) ausprobiert wurden.
Hier ist ein funktionierender Code, der die Suche beendet, sobald er eine Lösung gefunden hat. (Es könnte kleinere Summen mit der gleichen Anzahl von Summanden geben). Es ist in Python, aber das ist praktisch Pseudo-Code: -)
%Vor%Dies soll eine Lösung in der kleinsten Anzahl von Vergleichen finden. Wenn Sie auch möchten, dass die Summe minimal ist, dann erzeugen Sie bei jeder Größe n alle n-Teil-Summen auf einmal, sortieren Sie sie und überprüfen Sie sie in aufsteigender Reihenfolge.