Algorithmus muß zu einer Gruppe von Dateien unterschiedlicher Größe in etwa gleiche Blöcke
-
13-09-2019 - |
Frage
Ich versuche, einen Algorithmus, um herauszufinden, die mich Gruppe eine Auswahl von Dateien unterschiedlicher Größe in etwa ‚n‘ Gruppen von ungefähr gleicher Größe helfen.
Alle Ideen, wie dies zu erreichen?
Lösung
Find the target group size. This is the sum of all sizes divided by n.
Create a list of sizes.
Sort the files decreasing in size.
for each group
while the remaining space in your group is bigger than the first element of the list
take the first element of the list and move it to the group
for each element
find the elemnet for which the difference between group size and target group size is minimal
move this elemnt to the group
Dies erzeugt keine optimalen Ergebnisse, sondern ist einfach zu implementieren und bekommt man gute Ergebnisse. Für die optimale Lösung benötigen Sie eine erschöpfende Suche, die NP abgeschlossen ist.
Andere Tipps
K bedeutet könnte Ihnen helfen. Es ist ein guter Ausgangspunkt, um erweiterte Clustering-Algorithmen zu erforschen, aber wenn man bedenkt, dass Ihr Problem 1-dimensionalen, k-Mittel sollten mehr als genug sein.
Ihr implizites Optimierungsziel ist höchstwahrscheinlich n, die Anzahl der Gruppen zu minimieren. Dann haben Sie genau die Bin Packing Problem , manchmal auch als die Schneidgut Problem .
Netlib hat diese Fortran Code die allgemeinere mehr Ranzen Probleme zu lösen (Produkte haben Gewinn sowie Kosten / Gewicht-Werte).