Gruppiertes Sortieren

[sx2008]

Das Problem ist wohl eine Variante des Rucksackproblems.
Ich würde es so probieren:
Bei 20 Elementen werden 20/4 = 5 Töpfe gebildet.
Jeder Topf erhält am Anfang zufällig ausgewählt 4 Elemente.
[ Start ]
Die Summen aller 5 Töpfe werden berechnet.
Dann werden die beiden Töpfe mit der grössten Abweichung ausgewählt.
Sollte die Abweichung geringer als ein vorgegebener Maximalwert sein, wird der Algorithmus beendet.
Diese beiden Töpfe tauschen nun ihre Elemente.
Bei 4 Elementen gibt es 4 *4 = 16 Tauschmöglichkeiten.
Alle Tauschmöglichkeiten werden durchprobiert und der Tausch durchgeführt,
bei dem der Unterschied der Summe minimal wird.
Die nächste Iteration wird eingeleitet (Goto [ Start ]) oder der Algorithmus nach einer max. Anzahl von Iterationen beendet.

Die ideale Lösung wird so vielleicht nicht gefunden, aber es wird doch ein relativ guter Ausgleich erreicht.

[Lee500]

Danke sx2008,

Das ist eine Lösung die sich erstmal ganz gut anhört, aber heute nacht habe ich nicht mehr die Motivation dazu

Ich werd das mal ausprobieren.

Gruß
Lee500

//EDIT: Ich habe es jetzt am laufen. Ist nicht ganz so gelöst wie oben, da er dann immer zwischen den selben Töpfen hin und hergetauscht hat. Jetzt sucht er sich den schlechtesten Topf und sucht sich dann ein Element eines anderen Topfes, dessen Tausch beide Töpfe näher an den Optimalwert bringen. Diese Schleife läuft dann solange, bis kein Tausch mehr gefunden wird, von dem beide Töpfe profitieren würden.