Zahlenreihe in zwei Teile zerlegen -> gleiche Summen

[xaromz]

Hallo,

ich möchte gerne eine Zahlenreihe (z.B. 11, 5, 9, 6, 9) in zwei Teile zerlegen, so dass die beiden Teile eine möglichst gleiche Summe haben.
In diesem Fall wären das zwei mal 20 (11 + 9, 5 + 6 + 9).

Gib es dafür einen Algorithmus?

Gruß
xaromz

[thkerkmann]

Hi,

1. bilde die Summe der ganzen Reihe
2. teile durch 2 = dein Grenzwert
3. sortiere die Reihe absteigend
4. Verteile die Zahlen abwechselnd auf die zwei Stapel bis Grenzwert erreicht

So würde ich das machen :-)

Gruss

[xaromz]

Hallo,

damit sind aber leider nur Näherungswerte möglich. Bei dem Beispiel 4, 4, 5, 11, 16 (halbe Summe 20) kommt dann z. B. 16 + 5 = 21, 11 + 4 + 4 = 19 raus. Besser wäre aber 16 + 4 = 20, 11 + 5 + 4 = 20.
Bei extremeren Werten könnte sich das noch mehr verschieben.

Gruß
xaromz

[himitsu]

im Grunde isses am Einfachsten alle möglichen Kombinationen durchzuprobieren und die Erste mit der kleinsten Abweichung vom Mittelwert zu nehmen.

[xaromz]

Hallo,

druchprobieren geht bei ein paar Zahlen schon, aber wenn die Liste länger ist, dann explodiert der Aufwand. Das würde ich eher ungern machen.

Gruß
xaromz

[Panthrax]

1. bilde die Summe der ganzen Reihe
2. teile durch 2 = dein Grenzwert
3. sortiere die Reihe absteigend
4. Verteile die Zahlen auf 2 Stapel, wobei der jeweils kleinere die nächste Zahl erhält.

Ist aber auch nicht perfekt:

Code:

(7, 7, 5, 3, 3, 3) : 28

(7,    5,       3) : 15
(   7,    3, 3,  ) : 13

(7, 7            ) : 14
(      5, 3, 3, 3) : 14

Dabei sah es so gut aus... :cyclops:

[Gausi]

Das Problem nennt sich PARTITION und ist (schwach) NP-vollständig. Einen wirklich effizienten Algorithmus gibt es also höchst wahrscheinlich nicht.
Wenn die Zahlenwerte aber alle nicht zu groß sind, lässt sich das mit dynamischer Programmierung in (pseudo)polynomieller Zeit lösen (ist ja nur schwach NP-vollständig ;-)), mehr dazu in der Wikipedia:

http://en.wikipedia.org/wiki/Partition_problem
http://en.wikipedia.org/wiki/Subset_sum_problem (da wird ein Algorithmus dazu erläutert, den man für Partition leicht modifizieren müsste)

[ThomasNds]

Hallo,

wie mein Vorposter schon sagte: das Problem ist bekannt als subset-sum-problem oder binärer Knapsack, z.B.: http//www.cs.umu.se/kurser/TDBA77/VT06/algorithms/BOOK/BOOK4/NODE145.HTM oder http://www.brpreiss.com/books/opus4/html/page447.html. Google-Suchwörter sind Knapsack, subset sum, Teilsummenproblem, Untersummenproblem, Partitionieren, Balancing Scales problem.
Das Problem ist NP-schwer. Bei kleinen Problemen ist die beste und einfachste Lösung ein Ausprobieren aller sinnvollen(!) Partitionen.

Man reduziert das Problem darauf, aus einer gegebenen Menge zahlen solche auszuwählen, daß eine bestimmte Zielsumme das Ergebnis ist. Sinnvoll ist es, mit den größten Kandidaten anzufangen. Erster Schritt also: Sortieren. Dann Summe der Werte bilden. Zielsumme ist die Hälfte. Lösung per Backtracking.

Ziesumme null: Lösung ist die leere Menge
Sonst: wähle den ersten Kandidaten, suche Lösung
für Zielsumme-Kandidat(gibt Lösungen, die Kandidat enthalten)
dann schließe aktuellen Kandidaten aus, suche Lösung für
Zielsumme (gibt Lösüngen, die Kandidat nicht enthalten).

Wenn die verbleibenden Kandidaten nicht ausreichen, um die Zielsumme zu ergeben, kann man abbrechen.

Mal so aus der hohlen Hand:

Code:

werte: Array [1 .. N] of Integer = {16,14,6,7,2,1}
Kandidaten: Array [1 .. N ] of Bolean =
{false,false,false,false,false,false}
Kandindex:Integer = 1;
SummerestKandidaten: Integer;

Function löse(kandidat:Integer; Zielsumme:Integer):Boolean

Begin
if Kandidat >N then return false;

if Summe < 0 then return false;
If Summerestkandidaten<Zielsumme return false;
(*Auch wenn alle übrigen Kandidaten gewählt werden,
erreichen wir die Zielsumme nicht->weitermachen lohnt
nicht*)

if summe=0 then
    Lösung ausgeben
    return true
endif

(*Kandidat einschließen*)
Kandidaten[Kandidat]=true; 
Summerestkandidaten:=Summerestkandidanten - wert[Kandidat];
if löse(Kandidat +1, Zielsumme - werte[Kandidat]) then
    return true (*Abbruch der weiteren Suche, da Lösung
gefunden*)

(*Mit Kandidat keine Lösung gefunden, also mal ohne ihn
versuchen*)
Kandidaten[Kandidat]:=false;
if löse(Kandidat+1, zielsumme) then return true

(*auch ohne Kandidat keine Lösung gefunden*)
(*Änderungen rückgängig machen, damit obere Ebenen nicht
irritiert werden*)
Kandidaten[Kandidat]=false;
Summerestkandidaten:=Summerestkandidanten + wert[Kandidat];
return false
endfunc

Begin Main
Setze Summe =Summe(werte)
Summerestkandidaten:=Summe;
Zielsumme=Summe/2
löse(1, Zielsumme)

Enthält bestimmt noch Fehler.

Gruß

T.

[edit=mkinzler]Code-Tag eingefügt Mfg, mkinzler[/edit]

[thkerkmann]

Genau, das ist der 5te Punkt, den ich vergessen habe.

5. optimieren per Backtracking

:thumb: