PHP größte ganze Zahl aus Summe unsortierter Array

Ich würde vorschlagen, das ganze Array zu summieren und dann die kleinste Summe mit dem Dezimalteil zu finden, der dem der gesamten Summe entspricht. Wenn die Zahlen nicht eine sehr hohe Genauigkeit nach dem Dezimalpunkt haben, was auch immer der Ansatz zum Finden der genauen Zahl ist, sollte diese Umkehr viel Rechenleistung einsparen.

Auch das Sortieren des Arrays und das Gierige aus den kleinsten Zahlen ergeben gute Ergebnisse. Die optimale Lösung hängt jedoch stark von der Art der ursprünglichen Menge ab. Könnten Sie näher spezifizieren, welche Art von Zahlen Sie erwarten?

Der Großteil dieses Codes dient zum Abrufen der Permutationen eines Arrays. Ich bin mir sicher, dass es optimiert werden kann, aber das berechnet 3 Arrays mit Längen von 4, 5 und 6 in 45ms auf einem einzelnen Xeon-Quad-Core-Server. Springt auf etwa 220 ms, wenn ich ein viertes Array mit 7 Dezimalstellen hinzufüge, und satte 2 Sekunden, wenn ich ein Fünftel mit 8 hinzufüge.

Im Grunde werden alle Permutationen des Arrays, das die Floats enthält, abgerufen, und jedes einzelne wird Schlüssel für Schlüssel addiert, und wenn die Summe eine ganze Zahl größer als die aktuelle ganze Zahl ist, wird diese Zahl aktualisiert. Schließlich die größtmögliche Anzahl zurückgeben.

Das Guthaben für die Array-Permutationsfunktion geht an dirk dot avery a t gmail at http://php.net/manual/en/function.shuffle.php

Das ist ein großes Problem, über das man nachdenken sollte. Aus der Spitze meines Kopfes, das ist der Pseudocode, den ich verwenden würde:

1. A = Array von Elementen.
2. A '= sortiertes Array von Elementen.
3. S = Summe aller Elemente.
4. Während A 'nicht leer ist:
   1. V = ganzzahliger Teil von S.
   2. R = Rest von S = S - Stock (S)
   3. Erstellen Sie eine temporäre Kopie von A ', X.
   4. Iterate von größten zu kleinsten Werten von X als X [i]:
      1. Wenn X [i] & lt; R, subtrahiere X [i] von R. Entferne X [i] von X.
      2. Wenn R == 0, haben wir die Lösung gefunden. V ist die ganze Zahl, X enthält die Summanden. STOP.
   5. Wenn X leer ist, gibt es keine Lösung. STOP.
   6. Reduziere S um den größten Wert in A '. S = S - Max (A '). Entferne Max (A ') von A'.
5. Gehen Sie zurück zu Schritt 4.

Natürlich musste ich sehen, ob das tatsächlich funktionieren würde. Hier ist der (sehr unordentliche, Wegwerf-Qualität) Code, den ich geschrieben habe, um es zu testen:

Es ist ein hässlicher O (N ^ 2) Algorithmus, aber er sollte korrekt sein. Kann jemand ein anfängliches Array sehen, wo dies fehlschlagen würde?

Aus Spaß habe ich mit einem Array von 50 Elementen versucht und die erste Zeile durch folgende Zeilen ersetzt:

Auf einen Blick sieht es richtig aus - ich überlasse die Bestätigung jemand anderem;)