Как разбить массив на группы с равными суммами в каждой группе?

Question

[FlashHaos]

Коллеги, подскажите алгоритм, которым можно разбить массив чисел на n групп так, чтобы суммы чисел в каждой группе были максимально близки?

Answer 1

[xmoonlight]

Сумму всего массива нужно разделить на кол-во групп (ср.арифметическое число в группе, к которому будем стремиться) и по-очереди набирать в группы, начиная с самой большой цифры (значения элемента) из массива. Как только сумма в группе превысит среднее арифметическое - пропустить и перейти к следующей группе и так до тех пор, пока не останется самое меньшее из всего массива, которое после 1-го цикла превышения попадает в группу с самым минимальным превышением целевой суммы.
PS: нескромный вопрос можно: а зачем такое может пригодиться?

Comments

[FlashHaos]

Попробую, спасибо. Цель - разбить сессию резервного NAS-ресурса с рядом каталогов на потоки так, чтобы время общего бекапа было минимальным. Если скорость каждого потока равна - то проще всего выровнять эти потоки.

[xmoonlight]

FlashHaos: сначала полный (и раз в пол-года), затем периодические инкрементальные (по изменению или раз в N-часов) бэкапы не спасают?

Потоков - много, а скорость считывания с СХД - не упадёт при нескольких потоках? Иными словами: [кол-во потоков]*[скорость потока]*[размер в одном потоке]>[скорость одного потока]*[общий размер] ?

Разные цифры - это размеры каталогов?
NAS - на чем? (ПО, железо какое?)

[FlashHaos]

Ну для конкретного случая - полный раз в неделю, дифференциальные раз в день, срок хранения - две недели. Таким образом плюс достигаются адекватные объемы, учитывая коэффицент дедупликации и хорошая скорость восстановления. Объемы большие, изменений много, так что делать полный реже - не уверен, что хорошая идея. Хотя, конечно, считать надо такие вещи. Если бы еще знать как это посчитать...

Да, цифры - это размеры каталогов. Каждый поток идёт на отдельное устройство резервного копирования, и по какой-то из причин один поток или множество (до восьми) - на каждый поток идёт равная скорость, меньше, чем потолок на стороне библиотеки или SAN.

Железо в данном кейсе - EMC VNX, ПО СРК NetBackup.

[xmoonlight]

FlashHaos: Нужны параметры: скорость изменения данных на рабочей СХД (Мб/с) и скорость одного бэкап-потока (тоже, Мб/с). Тогда можно посчитать минимальный промежуток для дифференциального (пакетного) или дифференциально-пофайлового (сразу же по событию изменения одиночного файла, если есть такая возможность после вычислений).

Answer 2

[Андрей]

Читайте алгоритмы задачи об укладке рюкзака - у Вас получается ее разновидность с общим штрафом по нескольким рюкзакам.

Comments

[FlashHaos]

К сожалению, я совсем не математик. Можно пояснить, как применить данную задачу в моём случае? Про несколько рюкзаков я не нашел.