C #: код для максимально эффективного размещения большого количества файлов на DVD

Question

Мне нужно написать приложение, которое возьмет список файлов (некоторые большие, некоторые маленькие) и поместит их на DVD (или CD, или что-то еще) настолько эффективно, насколько это возможно. Весь смысл этого приложения состоит в том, чтобы израсходовать как можно большую часть 1-го диска перед переходом на 2-й диск, максимально заполнить 2-й диск до перехода на 3-й диск и т. Д.

(Примечание: приложение не должно выполнять фактическую запись на DVD, оно просто должно найти наилучшее возможное соответствие).

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

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

Есть идеи? И, как всегда, C # код всегда ценится.

Answer 1

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

Answer 2

Простой алгоритм:

1. Сортировка списка файлов по размеру файла
2. Найдите самый большой файл, который меньше оставшегося свободного места на DVD, и добавьте его на DVD.
3. Если оставшееся свободное дисковое пространство DVD меньше, чем у остальных файлов, запустите новый DVD.
4. Повторите с 2.

Answer 3

Для всех, кто еще интересуется этим вопросом ... Я написал утилиту, которую я использовал для аналогичной цели - встраивать файлы в набор дисков / дисков. Он использует интерфейс командной строки / файла. Доступны версии на C, C ++ и Java (не на C #).

http://whizman.com/code/diskfit.tgz

Более подробная информация находится в файле diskfit.tgz: Doc / diskfit.txt.

(AGPL3)

Мы могли бы охарактеризовать вопрос как множественный рюкзак 0-1, или линейная упаковка бен. (Спасибо jon-skeet за ссылку о проблеме с рюкзаком.)

Dthorpe решает линейную упаковку бункеров, для того, чтобы точно соответствовать бункерам / дискам все файлы [хорошо O (n) или O (n lg n) быстро - также возможно в электронной таблице без писать сценарий].

По существу, diskfit (вышеуказанная утилита) выводит подходящие наборы файлов основанный на 0-1 одноместном ранце, и пользователь выбирает наборы файлов на один диск для сборки в набор дисков - помощь пользователю (но не полностью автоматизация) в обоих направлениях:

• линейная упаковка бункера - для полного набора дисков;
• 0-1 множественный рюкзак - для каждого поднабора дисков 1..k полного набора дисков (где файлы имеют приоритет, иначе различаются по значению).

Полный программный выбор полного комплекта дисков, будет дополнительной функцией. Было бы недостаточно применить 0-1 раствор для одной рюкзака, автоматически диск за диском [жадно]. (Рассмотрим 3 рюкзака вместимостью 6 и доступные предметы с одинаковой ценностью и веса: {1, 1, 2, 2, 3, 4, 5}. Применение 0-1 ранца к первому ранцу изолированно выберет {1, 1, 2, 2} для получения суммы 4, после которой мы не можем уместить все оставшиеся 3 предмета в оставшихся втором и третьем рюкзаках - в то время как мы знаем, что можем поместить все предметы в 3 рюкзака как {1, 2, 3} & {1, 5} & {2, 4}.)

Answer 4

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

РЕДАКТИРОВАТЬ: одна проблема, с которой вы столкнетесь, заключается в том, что если один из ваших файлов больше, чем размер вашего носителя, вы не сможете записать этот файл.

Answer 5

for each file
 is there enough room this dvd?
   yes, store it here
   no, is there room on another already allocated dvd?
     yes, store it there
     no, allocate another dvd and store it there

Answer 6

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

Предположим, у нас есть неограниченный список дисков.Возьмите каждый файл в порядке убывания по размеру, затем добавьте каждый файл на первый диск, в который он вписывается. Это называется «Уменьшение по первому размеру» и в худшем случае занимает 11/9 OPT + 6/9 дисков.Если вы выбираете файлы в случайном порядке, вам вместо этого нужно 11/9 дисков OPT + 1.

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

Answer 7

Я нашел много инструментов, которые должны решить эту проблему, но все они стараются свести к минимуму ОБЩЕЕ количество используемых дисков, в то время как меня просто интересовало подмножество файлов SINGLE, которые лучше всего подходят для диска SINGLE.

Итак, я закончил писать свой собственный инструмент под названием " ss " (из алгоритма "сумма подмножеств", который основан на). Инструмент все еще глючит и не может восстановить каталоги, но он работает для меня. :)

Answer 8

используйте возврат для отслеживания, чтобы получить оптимальный набор файлов для записи на DVD-диск 1, затем исключите их из списка и используйте возврат на оставшиеся файлы для получения оптимального заполнения для DVD-диска 2 и т. Д.

Answer 9

Как насчет того, чтобы начать с того, что вы поместили как можно больше самых больших файлов на один DVD, а затем заполнили его как можно большим количеством самых маленьких файлов (начиная с самых маленьких).

Повторите этот процесс с оставшимися файлами для каждого диска.

Я не уверен, что это даст вам идеальное освещение / распространение, но я думаю, что это может каким-то образом решить ваши потребности.