Einzelnen Beitrag anzeigen

Benutzerbild von sx2008
sx2008

Registriert seit: 16. Feb 2008
Ort: Baden-Württemberg
2.332 Beiträge
 
Delphi 2007 Professional
 
#4

AW: Gruppiertes Sortieren

  Alt 31. Okt 2010, 23:37
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.
  Mit Zitat antworten Zitat