✔ Optimale Verteilung von Elementen

[skee]

Hallo,

Aktuell muss ich mein Problem in PHP lösen, daher wäre vielleicht eine Antwort für PHP ganz nett, aber da ich das Problem grundsätzlich verstehen will, nehme ich auch andere Sprachen, oder allgemeine Hilfen

Ich habe mehrere Gruppen, welche jeweils x Elemente enthalten. Jetzt möchte ich diese Gruppen zusammenfassen, so dass jede Zusammenfassung maximal 64 Elemente beinhaltet. Die Gruppen sollen dabei immer zusammenbleiben und komplett in eine Zusammenfassung kommen.
Und natürlich möchte ich das ganze so optimal wie möglich machen, dass es möglichst wenig Zusammenfassungen gibt.

Aktuell mache ich es so, dass ich mir in einer Schleife jeweils die größte Gruppe, die noch reinpasst, hole und hinzufüge. Und wenn die noch verfügbaren Gruppen zu groß für den verbleibenden Platz der Zusammenfassung sind, mache ich eine neue und hole mir wieder die größte Gruppe die reinpasst,usw. Funktioniert zwar technisch, hat aber den Nachteil, dass meistens am Schluß noch ungenutzter Platz übrig bleibt, wo noch ein paar der kleinen Gruppen reingepasst hätten.

Hat jemand eine Idee, wie ich das halbwegs performant optimieren könnte?

Gruß
Skee

 

[sheel]

Hi

das ist ein NP-hartes Problem; die optimale Lösung zu berechnen ist also nicht effizient möglich
("jede mögliche Belegung durchprobieren" könnte das Schnellste sein, wenn man wirklich die
beste Lösung braucht. Evt. muss man nicht wirklich alles probieren, aber größenordnungsmäßig
ist es so umständlich). http://en.wikipedia.org/wiki/Bin_packing_problem

Bei zB. 10 Gruppen, die aufzuteilen sind, kommt man (mit einem naiven n^n) schon auf
10000000000 verschiedene Möglichkeiten zu probieren (wie gesagt gibt es evt. "kleinere"
Verbesserungsmöglichkeiten, aber nichts wirklich Tolles)

Dein Ansatz klingt als Annäherung schon nicht schlecht.

 

[ikosaeder]

Hast du noch ein paar Details? Wie groß sind die Gruppen?
Als erstes würde ich die Elemente der Größe nach sortieren. In die erste Zusammenfassung solange Gruppen packen, bis die nächste Gruppe nicht mehr passt. Dann nimmst du dir die nächste Zusammenfassung vor. Das machst du bist die Hälfte der Elemente einsortiert sind. Mit der anderen Hälfte füllst du die Lücken auf.

 

[skee]

Ja, sowas hatte ich schon vermutet.
Danke dir!

 

[skee]

Die Gruppen sind zwischen 5 und 30 Elemente groß.