Sortierung einer Menge auf gleichmäßigen Betrag

Question

Hallo zusammen,


ich habe ein Problem, über das ich bereits länger nachgedacht habe. Vermutlich gibt es eine einfache Lösung, aber ich habe ein Brett vor dem Kopf und hoffe ich bin hier richtig :)

Aufgabe:

Gegeben sei eine Menge n * k Bauklötzen mit unterschiedlichen Höhen.

Ziel ist das Errichten von n Türmen mit k Bauklötzen. Die Klötze sollen dabei so auf die Türme verteilt sein, dass alle Turme möglichst wenig Höhendifferenz zueinander haben.

Problem/Ansatz:

Die einzige Lösung auf die ich gekommen bin, um das Problem zu lösen und garantiert die beste Lösung zu bekommen, wäre alle Lösungen durchzuprobieren und dann die Ergebnisse zu vergleichen. Das "Bruteforce" Vorgehen ist allerdings alles andere als effizient.

Gibt es eine geschickte Methode, um die Bauklötze zu sortieren und einen minimalen Fehler in der Abweichung zu bekommen?

Vielen Dank!

Answer 1

Um mal einen Anfang zu machen:

Mit der Software meines Vertrauens, auch wenn das z.Z. gelitten hat,

Generiere 20*6 Bauklötze mit den Höhen zwischen 4 und 10, sortiert und der Reihe nach in die Türmchen geschoben

Frage: Soll das aufgehen - hier glatter Durchschnitt TBHΘ=140 pro Turm

Jetzt könnten man umsortieren

- von denen die zuviel erwischt haben zu denen die zu flach gebaut haben

Sollte doch ein ziemlich optimales Ergebnis bringen?

Comments

Danke für deine Antwort!

Den Ansatz die Türme nacheinander aufzufüllen macht zwar Sinn, bringt für sich aber noch nicht das optimale Ergebnis (s. unten).

Die Krux ist deshalb vmtl. das Umsortieren, das du bereits angesprochen hast. Dabei ist aber die Frage, wie man die Klötze geschickt sortiert/umtauscht, um die bestmögliche Höhe zu erreichen. Insbesondere wenn man Turmhöhen mit zufälligen, reellen Zahlen betrachtet, sodass es unwahrscheinlich ist, dass dieselbe Höhe zwei mal in der gegebenen Menge auftritt'.

Bei dem Beispiel unten ist das noch relativ einfach, aber bei mehr Klötzen/Türmen wird die Umsortierung wieder schwieriger. Insbesondere wenn man eben nicht alle Kombinationen durchprobieren möchte.