Besoin d'algorithme pour regrouper des fichiers de différentes tailles en blocs à peu près égales
-
13-09-2019 - |
Question
Je suis en train de trouver un algorithme qui va me aider groupe un assortiment de fichiers de différentes tailles en dire, « n » groupes de taille à peu près égale.
Toutes les idées sur la façon d'y parvenir?
La solution
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
Cela ne produit pas des résultats optimaux, mais il est facile à mettre en œuvre et vous obtient de bons résultats. Pour la solution optimale, vous avez besoin d'une recherche exhaustive qui est NP complet.
Autres conseils
K signifie pourrait vous aider. Il est un bon point de départ pour la recherche sur les algorithmes de regroupement plus avancés, mais étant donné que votre problème est de dimension 1, k-moyens devrait être plus que suffisant.
Votre objectif d'optimisation implicite est le plus susceptible de minimiser n, le nombre de groupes. Ensuite, vous avez exactement le de , parfois appelée coupe problème stock.
Netlib a cette Fortran pour résoudre le problème plus général plusieurs havresac (articles ont profit en tant que valeurs et coût / poids).