Задача похожа на задачу о рюкзаке, но немного отличается.
Имеется большое количество файлов (допустим, 500) - все разного объема, от 10мб до 5гб (но файлов до 100мб намного меньше). Количество файлов и их объемы заранее известны. Также имеется неограниченное (неограниченное, потому что количество не важно) количество флешек объемом 8Gb. Задача - как можно компактнее разместить все файлы на как можно меньшем количестве флешек. Не важно, как будут мешаться между собой файлы. Главное - чтобы на каждую флешку файлы записывались таким образом, чтобы на ней оставалось как можно меньше свободного (неэффективно используемого) места.
И, заполняя одну флешку, нужно учитывать, что далее будут заполняться и другие флешки. И, возможно, какой-то из файлов будет лучше записать на другой носитель, чтобы эффективнее его заполнить.
Вот такой алгоритм мне нужно реализовать. У вас прошу только подсказать уже существующий алгоритм (если что-то подобное уже существует) или слегка направить на правильный путь, указав, на что следует обратить внимание при написании своего алгоритма с нуля
*offtopic* Лет 15 назад делал такое для записывания анимешных сериалов на CD-диски, только там было сложнее, потому что сериалы можно разбивать по нескольким дискам и записывать можно толко сериалы целиком. Эх... было время. Сейчас эти 300 дисков даже и прочитать-то нечем. И исходники пропали лет 10 назад =(.
Как вам уже написали - эта задача о мульти-рюкзаке. Простого и эффективного решения у нее нет.
Однако, на практике, скорее всего, вам не нужно оптимальное решение - нужна лишь его некоторая аппроксимация. Посмотрите задачу о рюкзаке. Там есть очень простое динамическое программирование с параметрами вида "можно ли используя файлы с 1 по i-ый заполнить ровно k (мега|кило)байт"
Потом сморите в конце массива для всех файлов - это оптимальные заполнения одной флешки.
Удалите файлы определенные на эту флешку из рассмотрения и повторяйте процесс.
Можно навесить сверху полный перебор с отсечениями. Из массива ДП идля задачи о рюкзаке можно случайным образом получить несколько хороших заполнений.
Потом в переборе пробуйте разные варианты, запускайтесь рекурсивно. Какой-то ответ будет найден моментально. Выходите из перебора, если текущее количество флешек/общее свободное место/сумма квадратов свободных мест превысило оптимальное найденное пока что.
Для ускорения можно округлить размеры файлов до мегабайта. Чем меньше разрешение - тем быстрее будет работать ДП. Еще можно отдавать предпочтение большим файлам в начале.
Альтернативно - составьте задачу целочисленного линейного программирование (integer linear programming) и натравите на нее какой-то из солверов. Они сейчас очень продвинутые. Правда тут уж как повезет. Может на вашей задаче вы ответа так и не дождетесь. В качестве переменных берите, что такой-то файл относится к такой-то флешке. Сумма по каждому файлу - ровно один. По каждой флешке сумма размеров файлов * на переменные <= размер флешки. Сумма свободных мест - минимизируется.
Возможно, можно составить квадратичную целевую функцию, я не знаю, что сейчас солверы умеют. Гуглите quadratic integer programming solver.
Если хотите минимизировать количество флешек, то можно завести еще переменные - занята ли флешка. Уравнения тут - эта переменная >= всех индикаторынх переменных для всех файлов для этой флешки. Целевая функция - сумма всех переменных занятости флешек.
Простой
Простой
