Thorsten83 - Di 13.04.10 13:28
Titel: Scheduling bzw. PARTITION

---

Hey,
mal eine blöde Frage...
Ich hab eine Multimenge von ganzen Zahlen und möchte die so in disjunkte Teilmengen aufteilen, dass die maximale Summe über die Elemente einer Teilmenge minimal wird...

Dachte eigentlich das ginge relativ einfach, indem man die Zahlen absteigend sortiert und dann der Reihe nach jeweils in die Teilmenge einfügt, deren Summe von Elementen minimal ist.

Damit wäre dann aber auch Partition gelöst, was ja wohl eher nicht der Fall ist... :D

Wo liegt der Denkfehler?
Habt ihr ein Beispiel, bei dem das nicht funktioniert?

Gausi - Di 13.04.10 13:40

---

Beispiel: 1,1,1,2,3 auf zwei Teilmengen. Dein "Sortier-Algorithmus" teilt die drei einser zuerst auf zwei Haufen auf
und fügt dann die zwei in den kleinen Haufen ein

Zuletzt kommt die drei auf den ersten Haufen

Optimal wäre aber


Edit: Merke grade, dass du absteigend sortieren willst. Ok, ist bei dem Besipiel besser, aber dann nimm halt z.B. 10, 10, 10, 8, 8, 8, 6. Dabei findet dein Verfahren auch nicht das Optimum, da alle drei 10er auf einen Haufen müssen, um zweimal 30 zu bekommen. ;-)

Thorsten83 - Di 13.04.10 14:58

---

Hey,
danke für die schnelle Antwort :)

Ich wollte aber zuerst die großen Jobs bearbeiten bzw. die großen Zahlen zuweisen, damit wäre die Reihenfolge dann:

{3}, {}
{3}, {2}
{3}, {2, 1}
{3, 1}, {2, 1, 1} <-- Optimum...

Gausi - Di 13.04.10 15:21

---

Ja, deswegen habe ich zwischendurch meiner Antwort was hinzugefügt. Nimm 10, 10, 10, 8, 8, 8, 6. Eine optimale Aufteilung wäre 10+10+10=30 und 8+8+8+6=30. Dein Algorithmus liefert 10+10+8=28 und 10+8+8+6=32.

Thorsten83 - Di 13.04.10 16:39

---

Subbi, danke!