dividiere die Liste in zwei Teile, deren Summe am nächsten ist

Das Problem ist NPC, aber es gibt einen Pseudo-Polynomalgorithmus dafür, das ist ein 2-Partition Problem, Sie können den Weg des Pseudo-Polynom-Zeitalgorithmus für Subset-Summe verfolgen, um dieses Problem zu lösen. Wenn die Eingabegröße polynomisch mit Eingabewerten in Beziehung steht, kann dies in Polynomialzeit erfolgen.

In Ihrem Fall (Gewichte & lt; 250) ist es polynomisch (weil Gewicht & lt; = 250 n = & gt; Summen & lt; = 250 n ^ 2).

Sei Summe = Summe der Gewichte, wir müssen ein zweidimensionales Array A erstellen und dann A, Column by Column

A [i, j] = wahr if (j == Gewicht [i] oder j - Gewicht [i] = Gewicht [k] (k ist in der Liste)).

Die Erstellung eines Arrays mit diesem Algorithmus erfordert O (n ^ 2 * sum / 2).

Endlich sollten wir die wertvollste Spalte finden, die einen wahren Wert hat.

Hier ist ein Beispiel:

Artikel: {0,1,2,3} Gewichte: {4,7,2,8} = & gt; Summe = 21 Summe / 2 = 10

Also, weil a [10, 2] == wahr ist die Partition 10, 11

Dies ist ein Algorithmus, den ich hier gefunden und ein wenig bearbeitet habe, um ihn zu lösen Dein Problem:

Ich habe gerade zuerst T [i] zurückgegeben, was wahr ist, anstatt T [N / 2] (in der Reihenfolge von max zu min) zurückzugeben.

Den Pfad zu finden, der diesen Wert liefert, ist nicht schwer.

Sie können dies als Rucksackproblem umformulieren.

Sie haben eine Liste von Artikeln mit dem Gesamtgewicht M, die in einen Behälter mit maximalem Gewicht M / 2 passen sollten. Die in den Behälter gepackten Gegenstände sollten so viel wie möglich wiegen, aber nicht mehr, als der Behälter fasst.

Für den Fall, dass alle Gewichte nicht negativ sind, ist dieses Problem nur schwach NP-vollständig und hat polynomielle Zeitlösungen.

Eine Beschreibung der dynamischen Programmierlösungen für dieses Problem finden Sie auf Wikipedia .

Dieses Problem ist mindestens so schwierig wie das NP-vollständige Problem Teilmengensumme . Ihr Algorithmus ist ein Greedy-Algorithmus. Diese Art von Algorithmus ist schnell und kann schnell eine ungefähre Lösung generieren, aber sie kann nicht die exakte Lösung für ein NP-vollständiges Problem finden.

Ein Brute-Force-Ansatz ist wahrscheinlich der einfachste Weg, um Ihr Problem zu lösen, obwohl es zu langsam ist, wenn zu viele Elemente vorhanden sind.

• Probieren Sie jede Möglichkeit aus, die Elemente in zwei Mengen zu partitionieren und berechnen Sie die absolute Differenz in den Summen.
• Wählen Sie die Partition, für die die absolute Differenz minimal ist.

Das Generieren aller Partitionen kann durch Berücksichtigung der Binärdarstellung jeder Ganzzahl von 0 bis 2 ^ n erfolgen, wobei jede Binärziffer festlegt, ob sich das entsprechende Element in der linken oder rechten Partition befindet.