Оптимальное сочетание файлов на блоки по 4,8 ГБ

Question

Мой накопитель имеет DMG-блоки. Сумма их размеров строго ниже 47ГБ. У меня 11 DVD, каждый размером 4,7 ГБ. Я хочу использовать как можно меньшее количество DVD без сжатия (проблема может быть излишней, так как она рассматривает наиболее оптимальные комбинации с точки зрения DMG-файлов. Вы можете подумать о сжатых файлах, если хотите. ).

Вы видите, что DMG-файлы имеют произвольные размеры. Так много возможных решений.

find . -iname "*.dmg" -exec du '{}' \; 3&> /dev/null

1026064 ./Desktop/Desktop2.dmg
5078336 ./Desktop/Desktop_2/CS_pdfs.dmg
2097456 ./Desktop/Desktop_2/Signal.dmg
205104  ./Dev/things.dmg
205040  ./Dev/work.dmg
1026064 ./DISKS/fun.dmg
1026064 ./DISKS/school.dmg
1026064 ./DISKS/misc.dmg
5078336 ./something.dmg

Файлы на DVD могут иметь произвольный порядок. Например, CS_pdfs.dmg и Signal.dmg не обязательно должны быть на каком-то диске.

Так как же найти способ использовать как можно меньше DVD-дисков?

Answer 1

Ваша задача называется математически проблемой упаковки бункера (которая связана с проблемой ранца .)

Так как np-hard , очень трудно решить это эффективно! Существует рекурсивное решение (динамическое программирование + возврат), но даже для этого может потребоваться много места и времени вычислений.

Самым простым решением является жадный алгоритм (см. Сообщение Блинди), но это может дать плохие результаты.

Это зависит от того, сколько предметов (n) вы хотите упаковать, и насколько точным должно быть решение (большая точность увеличит время выполнения!). Для малых n достаточно рекурсивного / грубого или обратного отслеживания, для больших проблем я бы посоветовал использовать некоторые метаэвристические - особенно генетические алгоритмы , которые работают достаточно хорошо и дают хорошие приближения в приемлемых временных интервалах .

Answer 2

Полностью альтернативное решение: используйте split и разделите границы на несколько DVD Вы получите 100% загрузку каждого диска, кроме последнего. http://unixhelp.ed.ac.uk/CGI/man-cgi?split

Answer 3

Вероятно, вам следует попробовать жадный алгоритм прежде всего - выбрать самый большой элемент, который может поместиться на оставшемся DVD каждый раз. Хотя это не гарантируется, но эта проблема является NP-полной, и эффективного решения не существует. У меня недавно была похожая проблема, и жадный алгоритм работал довольно хорошо в моем случае - возможно, он будет достаточно хорош и в вашем случае.

Answer 4

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