Wie finde ich die größtmögliche Summe der Elemente eines Arrays zu einem bestimmten Wert?

Sie würden normalerweise dynamische Programmierung für ein solches Problem verwenden. Dies läuft jedoch im Wesentlichen darauf hinaus, eine Menge möglicher Summen zu behalten und die Eingabewerte einzeln hinzuzufügen, wie im folgenden Code, und hat die gleiche asymptotische Laufzeit: O(n K) , wobei n die Größe Ihrer Eingabe ist Array und K ist der Zielwert.

Die Konstanten in der Version unten sind jedoch wahrscheinlich größer, aber ich denke, dass der Code viel einfacher zu folgen ist, als die dynamische Programmierversion wäre.

BEARBEITEN

Eine kurze Anmerkung zur Laufzeit könnte nützlich sein, da ich gerade O(n K) ohne Begründung angefordert habe.

Es ist klar, dass die Initialisierung und das Drucken des Ergebnisses nur konstante Zeit benötigen, also sollten wir die Doppelschleife analysieren.

Die äußere Schleife läuft über alle Eingaben, so dass ihr Körper n mal ausgeführt wird.

Die innere Schleife läuft bisher über alle Summen, was theoretisch eine exponentielle Zahl sein könnte. Allerdings verwenden wir eine obere Grenze von K , sodass alle Werte in sums im Bereich [0, K] liegen. Da sums eine Menge ist, enthält sie höchstens K+1 elements.

Alle Berechnungen innerhalb der inneren Schleife dauern konstant, so dass die gesamte Schleife O(K) benötigt. Die Menge newSums enthält aus dem gleichen Grund auch höchstens K+1 elements, so dass addAll am Ende auch O(K) benötigt.

Wrapping: Die äußere Schleife wird n mal ausgeführt. Der Schleifenkörper benötigt O(K) . Daher wird der Algorithmus in O(n K) ausgeführt.

BEARBEITEN 2

Auf Anfrage, wie man auch die Elemente findet, die zur optimalen Summe führen:

Anstatt eine einzelne ganze Zahl zu verfolgen - die Summe der Unterliste - sollten Sie auch die Unterliste selbst im Auge behalten. Dies ist relativ einfach, wenn Sie einen neuen Typ erstellen (keine Getter / Setter, um das Beispiel übersichtlich zu halten):

Die Initialisierung wird nun zu:

Die innere Schleife über sums benötigt ebenfalls kleine Anpassungen:

Sie können es als n-choose-k Problem für alle möglichen k sehen, so dass die Komplexität exponentiell ist .

1. Finden Sie eine Menge von Zahlen, die höchstens bis zu K summieren. Das Set sollte i numbers für i=1; i<=N; i++ enthalten. Um dies zu implementieren, nehmen Sie für jedes i einfach alle n-choose-i Kombinationen der Zahlen im Array.
2. Behalten Sie eine Variable finalResult mit dem besten bisher gefundenen Zahlensatz und ihrer Summe bei.
3. Vergleichen Sie jedes Unterergebnis von Schritt 1 mit dem finalResult und aktualisieren Sie es gegebenenfalls.

Es erinnert mich an das Knapsack-Problem , also sollten Sie es sich ansehen.

Ich würde sagen, sortiere zuerst das Array. Dann wäre Ihr Beispiel: arr = {5, 19, 23, 36, 40, 41}. Dann: 1) Nehmen Sie arr [0] und arr [i], wobei i = arr.Size ist. Summiere es und zeichne die Differenz zwischen der Summe und K auf, wenn die Summe kleiner als K ist. 2) Wenn Summe & gt; K, mach Schritt 1, aber statt arr [i], benutze arr [i-1], weil wir unsere Summe senken wollen.    Wenn Summe & lt; K, mach Schritt 1, aber statt arr [0], benutze arr [1], weil wir unsere Summe erhöhen wollen.    Wiederholen Sie Schritt 2, indem Sie entweder die Indizes erhöhen oder verringern, bis die Indizes für die beiden Elemente gleich sind. Dann kennen wir das Paar von Elementen, das den kleinsten Unterschied zwischen der Summe und K ergibt.

---------------- Bearbeitet für eine beliebige Anzahl von Elementen in der Lösung ----------------

Ich glaube, du brauchst vielleicht einen Baum. Hier ist, was ich denke:

1) Wählen Sie eine Nummer als obersten Knoten.

2) Erstellen Sie für jede Nummer in der Gruppe einen untergeordneten Knoten und für jede erstellte Zweigstelle    Berechnen Sie die Summe dieser Verzweigung.

3) Wenn die Summe kleiner als K ist, verzweigen wir erneut und erstellen untergeordnete Knoten für alle Elemente in der Menge. Wenn die Summe größer als K ist, hören wir auf, behalten den Unterschied zwischen der Summe und K (wenn Summe & lt; K). Wenn wir einen Zweig mit einer besseren Summe finden, behalten wir diesen Zweig. Wiederholen Sie diesen Vorgang, bis alle Zweige verzweigt sind.

Führen Sie die Schritte 1-3 mit verschiedenen Topknoten durch.