Precisa de Algoritmo para agrupar arquivos de tamanhos variados em blocos aproximadamente iguais
-
13-09-2019 - |
Pergunta
Eu estou tentando descobrir um algoritmo que vai me grupo uma variedade de arquivos de tamanhos variados em dizer ajudar, 'n' grupos de tamanho aproximadamente igual.
Algumas ideias sobre como conseguir isso?
Solução
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
Esta não produz os melhores resultados, mas é fácil de implementar e obtém bons resultados. Para a solução ideal você precisa de uma busca exaustiva que é NP completa.
Outras dicas
K significa pode ajudá-lo. É um bom ponto de partida para pesquisar algoritmos de agrupamento sobre mais avançados, mas dado que o seu problema é 1-dimensional, k-médias deve ser mais do que suficiente.
Seu objetivo implícito de otimização é mais provável para minimizar n, o número de grupos. Então você tem exatamente a bin packing problema , às vezes chamado de problema de corte de estoque .
Netlib tem essa fortran código para resolver o problema da mochila múltipla mais geral (itens têm lucro como valores bem custo / peso).