Meine Frage bezieht sich auf ein CodeFu-Übungsproblem (2012, Runde 2, Problem 3). Es kommt im Wesentlichen darauf an, ein Array von ganzen Zahlen in zwei (fast) gleiche Hälften aufzuteilen und den kleinstmöglichen Unterschied zwischen den beiden zurückzugeben. Ich habe die Problembeschreibung unten eingefügt. Wie in den Kommentaren erwähnt, kann dies als balanciertes Partitionsproblem beschrieben werden, was ein Problem im Bereich
Nun wurden ähnliche Probleme oft diskutiert, aber ich konnte keine effiziente Lösung für dieses Problem finden. Das Problem ist natürlich, dass die Anzahl der möglichen Kombinationen für einen Brute-Force-Suchlauf zu groß wird (zumindest bei Rekursion). Ich habe eine rekursive Lösung, die für alle außer den größten Problemsätzen funktioniert. Ich habe versucht, einige Optimierungen hinzuzufügen, die die Rekursion früh stoppen, aber die Leistung ist immer noch zu langsam, um einige Arrays der maximalen Länge (30) innerhalb des von CodeFu erlaubten 5-Sekunden-Maximums zu lösen. Vorschläge zur Verbesserung oder Neufassung des Codes wären sehr willkommen. Ich würde auch gerne wissen, ob es hilfreich ist, die iterative Version zu erstellen.
Update: auf dieser schönen Seite gibt es eine theoretische Diskussion des ausgewogenen Partitionsproblems, das eine gute Vorstellung davon gibt, wie man dieses Problem lösen und dynamisch lösen kann. Genau darum geht es mir, aber ich weiß nicht, wie ich die Theorie genau umsetzen soll. Der Film erwähnt, dass die Elemente in den beiden Untersammlungen "mit dem alten Trick der Rückzeiger" gefunden werden können, aber ich sehe nicht wie.
Sie und Ihr Freund haben eine Anzahl von Münzen mit verschiedenen Beträgen. Sie müssen die Münzen in zwei Gruppen teilen, so dass der Unterschied zwischen diese Gruppen in minimal.
z. Münzen der Größen 1,1,1,3,5,10,18 können geteilt werden als: 1,1,1,3,5 und 10,18 1,1,1,3,5,10 und 18 oder 1,1,3,5,10 und 1,18 Die dritte Die Kombination ist günstig, da in diesem Fall der Unterschied zwischen den Gruppen sind nur 1. Einschränkungen: Münzen haben zwischen 2 und 30 Elemente inklusive jedes Element der Münzen werden zwischen 1 und 100000 inklusive
Rückgabewert: Minimale Differenz beim Münzeinwurf möglich zwei Gruppen
HINWEIS: Die CodeFu-Regeln geben an, dass die Ausführungszeit auf dem CodeFu-Server nicht mehr als 5 Sekunden betragen darf.
Hier ist ein Beispiel für eine Menge, deren Lösung zu lange dauert.
{100000,60000,60000,60000,60000,60000,60000,60000,60000, 60000,60000,60000,60000,60000,60000,60000,60000,60000, 60000,60000,60000,60000,60000,60000,60000,60000,60000, 60000,60000,60000}
Wenn Sie den gesamten Quellcode möchten, habe ich ihn auf Ideone gestellt.
Sagen Sie N ist die Summe aller Münzen. Wir müssen eine Untermenge von Münzen finden, deren Summe der Summe ihrer Münzen am nächsten bei N/2 liegt. Lassen Sie uns alle möglichen Summen berechnen und wählen Sie die beste aus. Im schlimmsten Fall können wir 2 ^ 30 mögliche Summen erwarten, aber das mag nicht passieren, weil die größtmögliche Summe 100K * 30 ist, also 3M - viel weniger als 2 ^ 30, was etwa 1G wäre. Also sollte ein Array von 3M-Ints oder 3M-Bits ausreichen, um alle möglichen Summen zu halten.
Also haben wir Array a und a[m] == 1 wenn und nur wenn m eine mögliche Summe ist.
Wir beginnen mit einem zeroed Array und haben a[0]=1 , weil die Summe 0 möglich ist (man hat keine Münzen).
Wenn Sie in 30 * 3M Schritten fertig sind, werden Sie alle möglichen Summen kennen. Suchen Sie die Nummer m , die N/2 am nächsten ist. Ihr Ergebnis ist abs(N-m - m) . Ich hoffe, ich passe in Zeit- und Gedächtnisgrenzen.
Bearbeiten : Eine Korrektur ist erforderlich und 2 Optimierungen:
N+1 (einschließlich 0), um kleinere Münzsätze schneller zu lösen. m und N-m , reduzieren Sie die Array-Größe auf N/2 . Gebundene Prüfung für new_possible_sum hinzufügen. Werfen Sie größere mögliche Summen weg. BEARBEITEN nur um klar zu sein: Ich habe diese Antwort geschrieben, bevor die zusätzliche Einschränkung der Ausführung in weniger als fünf Sekunden in der Frage angegeben wurde. Ich habe es auch geschrieben, nur um zu zeigen, dass manchmal rohe Gewalt möglich ist, auch wenn es scheint, dass es nicht so ist. Diese Antwort soll also nicht die "beste" Antwort auf dieses Problem sein: Es ist genau gesagt eine Brute-Force-Lösung. Als Nebeneffekt kann diese kleine Lösung jemandem helfen, eine andere Lösung zu schreiben, um in einer akzeptablen Zeit zu verifizieren, dass ihre Antwort für "große" Arrays korrekt ist.
Das Problem ist natürlich, dass die Anzahl der möglichen Kombinationen zu Traverse wird bald zu groß für eine Brute-Force-Suche.
Angesichts des Problems, wie es ursprünglich angegeben wurde (bevor die maximale Laufzeit von 5 Sekunden angegeben wurde), bestreite ich diese Aussage völlig;)
Sie haben speziell geschrieben, dass die maximale Länge 30 ist.
Beachten Sie, dass ich nicht über andere Lösungen spreche (wie zum Beispiel eine dynamische Programmierlösung, die bei Ihren Einschränkungen funktionieren kann oder nicht).
Was ich sage ist, dass 2 30 nicht groß ist. Es ist ein bisschen mehr als eine Milliarde und das ist es.
Eine moderne CPU kann auf einem Kern Milliarden von Zyklen pro Sekunde ausführen.
Du musst nicht rekursiv sein, um das Problem zu lösen: Rekursives Verhalten sollte deinen Stack zerstören. Es gibt einen einfachen Weg, um alle mögliche Links / Rechts-Kombinationen zu bestimmen: einfach von 0 bis 2 exp 30 - 1 zählen und jedes Bit überprüfen (entscheiden, dass ein bisschen auf bedeutet, dass Sie den Wert nach links und aus setzen, dass Sie setzen der Wert auf der rechten Seite).
Wenn ich also die Problemaussage nicht falsch verstehe, sollte der folgende Ansatz ohne Optimierung funktionieren:
%Vor%Zum Beispiel:
%Vor%Auf einem Array von 30 Elementen läuft es auf meiner billigen CPU in 125 s. Das ist für einen "ersten Entwurf", eine völlig unoptimierte Lösung, die auf einem einzigen Kern läuft (das Problem ist, wie gesagt, trivial, um zu parallelisieren).
Sie können natürlich immer raffinierter werden und viele, viele und viele Zwischenergebnisse wiederverwenden und somit ein Array von 30 Elementen in weniger als 125 s lösen.
Tags und Links java arrays split performance recursion