Нужен алгоритм для группировки файлов разного размера в примерно равные блоки.

Question

Я пытаюсь придумать алгоритм, который поможет мне сгруппировать множество файлов разного размера, скажем, в группы примерно одинакового размера.

Есть идеи, как этого добиться?

Answer 1

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

Это не дает оптимальных результатов, но его легко реализовать и он дает хорошие результаты.Для оптимального решения необходим исчерпывающий перебор, NP-полный.

Answer 2

К означает может помочь вам.Это хорошая отправная точка для исследования более продвинутых алгоритмов кластеризации, но, учитывая, что ваша проблема одномерна, k-средних должно быть более чем достаточно.

Answer 3

Ваша цель неявной оптимизации, скорее всего, сведет к минимуму n — количество групп.Тогда у вас есть именно тот проблема с упаковкой мусорного бака, иногда называемый проблема с обрезкой запасов.

В Netlib есть это код Фортрана для решения более общей проблемы с несколькими рюкзаками (предметы имеют также значения стоимости/веса и прибыли).