Necesidad Algoritmo para archivos de distintas dimensiones aproximadamente iguales en bloques
-
13-09-2019 - |
Pregunta
Estoy tratando de averiguar un algoritmo que mi grupo ayudará a una variedad de archivos de diferentes tamaños en decir, 'n' grupos de aproximadamente el mismo tamaño.
Cualquier ideas sobre cómo lograr esto?
Solución
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
Esto no produce resultados óptimos, pero es fácil de implementar y que obtiene buenos resultados. Para la solución óptima que necesita una búsqueda exhaustiva que es NP completo.
Otros consejos
K significa podría ayudarle. Es un buen punto de partida para la investigación sobre algoritmos de agrupamiento más avanzados, pero dado que su problema es de dimensión 1, k-medios debería ser más que suficiente.
Es más probable que minimice n, el número de grupos de su objetivo de optimización implícita. Entonces usted tiene exactamente el los problemas de acumulación , a veces llamado el corte Stock problema .
código FORTRAN para resolver el problema más general de la mochila múltiple (artículos tienen el beneficio como valores de costo / peso así).