Sortieralgorithmus, zum erstellen zweier gleichgroßer Summen [gelöst]

[Francesco]

Guten Abend,

ich hänge seit einigen Stunden an einer Aufgabe und komme nicht weiter. Wir sollen einen Algorithmus in Pseudo-Code entwerfen, welcher eine endliche Liste von Werten (€)

$(w_1,...,w_n)$

bekommt und diese Werte dann in gleichgroße Summen aufteilt (Falls möglich).
Bsp.:

$w_1=1, w_2=7, w_3=5, w_4=2, w_5=1 \rightarrow w_2+w_5=w_1+w_3+w_4$

Meine herangehensweise, war es zuerst die Werte zu sortieren und neu zu benennen, sodass

$w_1>...>w_n,$

den Gesamtwert zu bestimmen, diesen zu halbieren, und zu schauen ob das größte w größer als der halbierte Gesamtwert ist (wir sollen auch schauen ob so eine Sortierung überhaupt möglich ist). Dann habe ich versucht zu schauen ob bei

$w_1=w_2+...+w_n, falls~nein\rightarrow w_1+w_n=w_2+...+w_{n-1}~falls~nein\rightarrow w_1+w_n+w_{n-1}=w_2+...+w_{n-2}\rightarrow...$

eine wahre Aussage herauskommt. Jedoch habe ich schnell gemerkt, dass diese herangehensweise falsch ist, und komme nun nicht weiter. Hat jemand eventuell einen Tipp oder Hinweis für mich?

Liebe Grüße
Francesco

[hustbaer]

Wenn es genau zwei gleich grosse Summen sein sollen, dann ist alles summieren und dann die Summe halbieren schonmal ein guter Anfang.

Du kannst dann auch noch den grössten Wert raussuchen und gucken ob der grösser als dieser Wert ist - und wenn ja, dann kannst du abbrechen. Das ist eine kleine Optimierung für einen speziellen "geht nicht" Fall. Ich würde das erstmal ignorieren.

Was dann übrig bleibt ist das Teilsummenproblem:
https://de.wikipedia.org/wiki/Teilsummenproblem
https://en.wikipedia.org/wiki/Subset_sum_problem

Und das ist NP-vollständig.

[Ein ehemaliger Benutzer]

@Francesco sagte in Sortieralgorithmus, zum erstellen zweier gleichgroßer Summen:

wir sollen auch schauen ob so eine Sortierung überhaupt möglich ist

Warum sollte eine Sortierung nicht möglich sein?

[Francesco]

Dieser Beitrag wurde gelöscht!

[Francesco]

@manni66 Wenn du zum Beispiel

$w_1=12, w_2=15, w_3=4, w_4=2$

hast, ist eine Sortierung von

$w_1,...,w_4$

in gleichgroße Summen nicht möglich.

[Ein ehemaliger Benutzer]

@Francesco sagte in Sortieralgorithmus, zum erstellen zweier gleichgroßer Summen:

@manni66 Wenn du zum Beispiel

$w_1=12, w_2=15, w_3=4, w_4=2$

hast, ist eine Sortierung von

$w_1,...,w_4$

in gleichgroße Summen nicht möglich.

Das „Sortierung“ zu nennen passt nicht zu

Meine herangehensweise, war es zuerst die Werte zu sortieren ...

[Francesco]

@manni66 Ist Aufteilung besser?

[Ein ehemaliger Benutzer]

@Francesco sagte in Sortieralgorithmus, zum erstellen zweier gleichgroßer Summen:

@manni66 Ist Aufteilung besser?

Ja dann kann man verstehen, wovon du jeweils sprichst.

[*john 0]

@hustbaer sagte in Sortieralgorithmus, zum erstellen zweier gleichgroßer Summen:

https://en.wikipedia.org/wiki/Subset_sum_problem

Und das ist NP-vollständig.

Bei der Aufgabenstellung musste ich gleich an das Rucksackproblem denken, was nur eine andere Formulierung des exakt gleichen Problems ist.