Алгоритм эффективного размещения?

Задача похожа на задачу о рюкзаке, но немного отличается.
Имеется большое количество файлов (допустим, 500) - все разного объема, от 10мб до 5гб (но файлов до 100мб намного меньше). Количество файлов и их объемы заранее известны. Также имеется неограниченное (неограниченное, потому что количество не важно) количество флешек объемом 8Gb. Задача - как можно компактнее разместить все файлы на как можно меньшем количестве флешек. Не важно, как будут мешаться между собой файлы. Главное - чтобы на каждую флешку файлы записывались таким образом, чтобы на ней оставалось как можно меньше свободного (неэффективно используемого) места.
И, заполняя одну флешку, нужно учитывать, что далее будут заполняться и другие флешки. И, возможно, какой-то из файлов будет лучше записать на другой носитель, чтобы эффективнее его заполнить.
Вот такой алгоритм мне нужно реализовать. У вас прошу только подсказать уже существующий алгоритм (если что-то подобное уже существует) или слегка направить на правильный путь, указав, на что следует обратить внимание при написании своего алгоритма с нуля
  • Вопрос задан
  • 344 просмотра
Пригласить эксперта
Ответы на вопрос 3
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
*offtopic* Лет 15 назад делал такое для записывания анимешных сериалов на CD-диски, только там было сложнее, потому что сериалы можно разбивать по нескольким дискам и записывать можно толко сериалы целиком. Эх... было время. Сейчас эти 300 дисков даже и прочитать-то нечем. И исходники пропали лет 10 назад =(.

Как вам уже написали - эта задача о мульти-рюкзаке. Простого и эффективного решения у нее нет.

Однако, на практике, скорее всего, вам не нужно оптимальное решение - нужна лишь его некоторая аппроксимация. Посмотрите задачу о рюкзаке. Там есть очень простое динамическое программирование с параметрами вида "можно ли используя файлы с 1 по i-ый заполнить ровно k (мега|кило)байт"

Потом сморите в конце массива для всех файлов - это оптимальные заполнения одной флешки.

Удалите файлы определенные на эту флешку из рассмотрения и повторяйте процесс.

Можно навесить сверху полный перебор с отсечениями. Из массива ДП идля задачи о рюкзаке можно случайным образом получить несколько хороших заполнений.

Потом в переборе пробуйте разные варианты, запускайтесь рекурсивно. Какой-то ответ будет найден моментально. Выходите из перебора, если текущее количество флешек/общее свободное место/сумма квадратов свободных мест превысило оптимальное найденное пока что.

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

Альтернативно - составьте задачу целочисленного линейного программирование (integer linear programming) и натравите на нее какой-то из солверов. Они сейчас очень продвинутые. Правда тут уж как повезет. Может на вашей задаче вы ответа так и не дождетесь. В качестве переменных берите, что такой-то файл относится к такой-то флешке. Сумма по каждому файлу - ровно один. По каждой флешке сумма размеров файлов * на переменные <= размер флешки. Сумма свободных мест - минимизируется.

Возможно, можно составить квадратичную целевую функцию, я не знаю, что сейчас солверы умеют. Гуглите quadratic integer programming solver.

Если хотите минимизировать количество флешек, то можно завести еще переменные - занята ли флешка. Уравнения тут - эта переменная >= всех индикаторынх переменных для всех файлов для этой флешки. Целевая функция - сумма всех переменных занятости флешек.
Ответ написан
Комментировать
Если задача практическая, то Multi-Part Zip поможет разбить файлы на множество томов.
Можно даже само-распаковывающийся архив создать.

Ну а если академическая, тогда гуглить Bin packing problem.
Ответ написан
Комментировать
LaRN
@LaRN
Senior Developer
То что вы описали похоже на задачу о раскрое материала. Вот тут посмотреть можно описание:
https://math.semestr.ru/lp/rask.php
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы