У меня есть куча мультимедийных файлов, которые я хочу записать на DVD, но, поскольку каждый DVD занимает только 4,5 ГБ, я должен найти оптимальный способ организации файлов, чтобы использовать минимальное количество DVD-дисков (в противном случае на каждом из них остается свободное место). DVD можно легко сложить). Есть ли инструменты, которые помогут с этим?
Много лет назад была DOS-утилита, которая делала это с дискетами.
Ах, проблема с рюкзаком. Я мог бы найти только один онлайн решатель для этого здесь. Ваш размер рюкзака будет 4,5 ГБ, а каждый пакет будет соответствовать размеру вашего файла. Вам нужно будет немного помассировать его вывод, чтобы он соответствовал вашему конкретному применению, но это должно быть работоспособно. Это не будет работать очень быстро, потому что эта проблема сложная.
Ответ Джеффа Шаттока верен: он эквивалентен (или изоморфен, как пишут математики) задаче комбинаторной оптимизации, но он эквивалентен одномерной задаче упаковки бинов, а не задаче о ранце.
К счастью для вас, у меня есть некоторый код, которым можно поделиться, который решит эту проблему для вас или любого другого, с доступом к компьютеру Windows с установленной по крайней мере версией 3.5 .NET Framework.
Сначала загрузите и установите LINQPad.
Во-вторых, скачайте запрос LINQPad, который я только что написал - вот linq (ha) в необработанный файл. Сохраните его как файл .linq и откройте его в LINQPad.
Измените параметры:
Вот часть кода запроса LINQPad, которую вы должны изменить:
int binSizeMb = 4476; // This is the (floor of the) total size of a DVD+R reported by CDBurnerXP.
string rootFileFolderPath = @"F:\2006 - Polyester Pimpstrap Intergalactic Extravaganza multicam";
Измените binSizeMb на размер вашего «bin», например, CD, DVD, ex. int binSizeMb = 650; для компакт-диска.
Примечание. Значение binSizeMb интерпретируется как то, что иногда называют мегабайтом. В отличие от моего детства, когда все кратные байты были «двоичными», иногда «МБ» теперь относится к «десятичному мегабайту» или ровно 1 000 000 байтов, в отличие от 1 048 576 байтов мегабайта (MiB), который используется в моем коде , Если вы хотите изменить это, измените строку const int bytesPerMb = 1048576; в коде const int bytesPerMb = 1000000; ,
Измените rootFileFolderPath на полный путь к папке, содержащей файлы, которые вы хотите «упаковать в контейнеры», например. string rootFileFolderPath = @"C:\MySecretBinFilesFolder"; ,
Запустите запрос, нажав F5 или нажав кнопку « Выполнить» в левом верхнем углу вкладки запроса.
Код запроса будет рекурсивно перечислять все файлы в папке rootFileFolderPath , то есть он будет также включать файлы во все подпапки.
Затем он создаст «корзины» для файлов, так что общий размер всех файлов в каждой корзине будет меньше или равен указанному размеру корзины.
На панели результатов LINQPad вы увидите два списка.
Первый список содержит все найденные файлы в порядке убывания по размеру.
Второй список - это корзины, созданные путем «упаковки файлов», со списком файлов и их размеров, а также оставшийся размер корзины.
Вот скриншот, показывающий второй список и первые две созданные корзины:
Согласно Википедии, алгоритм, который я использовал - стратегия First Fit Decreasing (FFD) - не должен быть слишком плохим; Википедия утверждает:
В 2007 году было доказано, что ограничение 11/9 OPT + 6/9 для FFD является жестким.
«ОПТ» относится к оптимальной стратегии (как нечто потенциально недоступное, а не какая-то конкретная фактическая стратегия).
Исходя из моих несколько нечетких воспоминаний о математических терминах, это должно означать, что стратегия FFD должна, в худшем случае, упаковывать элементы в ~ 1,22 раза больше ячеек, чем в оптимальной стратегии. Таким образом, эта стратегия может упаковать предметы в 5 корзин вместо 4. Я подозреваю, что его производительность, вероятно, будет очень близка к оптимальной, за исключением определенных «патологических» размеров элементов.
В той же статье Википедии также говорится, что существует "точный алгоритм". Я могу решить реализовать это тоже. Сначала мне придется прочитать статью, в которой описан алгоритм.
Попробуйте бесплатный DVD Span :
DVD Span - это инструмент резервного копирования для записи содержимого больших папок на несколько DVD. DVD Span может автоматически определять наилучшую организацию каждого диска, чтобы соответствовать максимальному количеству данных на минимальном количестве дисков. DVDSpan - отличный инструмент для резервного копирования музыкальной коллекции, фотографий или даже всего жесткого диска на DVD. А поскольку он производит обычные DVD-диски (или компакт-диски), не требуется никакого специального программного обеспечения для чтения или восстановления ваших резервных копий.
Также попробуйте Discfit, которая выбирает файлы и каталоги для копирования на различные диски:
Много лет назад я написал PHP-скрипт для решения этой задачи: https://bitbucket.org/borszczuk/php-backup-maker/
Вы можете взять один из вариантов программы в путеводителе автостопом по Haskell, возможно, после проработки некоторой части этого урока; учебное пособие написано с целью решения именно вашей проблемы распределения вещей на несколько дисков, в результате чего решение постепенно улучшается, что подтверждается следующим отрывком из главы 3 учебного пособия:
Уже достаточно предварительных экзаменов. давайте возьмем несколько компакт-дисков.
Как вы, возможно, уже поняли, наша проблема классическая. Это называется "проблема с рюкзаком" (если вы еще не знаете, что это такое, поищите в Google ). Есть более 100000 ссылок).
давайте начнем с жадного решения ...
Вот аналогичный вопрос (хотя и не тот же: его там не спрашивают об оптимизации), где вы можете найти более полезные решения / программы для вашей задачи (если они будут опубликованы):
В целом, код на Haskell довольно выразителен (поскольку Haskell - это язык для программирования на высоком уровне абстракции), и, следовательно, его легко понять.
Рассматривая код одного из решений, помните, что структура верхнего уровня программы, которую мы хотим написать, довольно проста, как изложено в главе 1 урока:
Теперь давайте немного подумаем о том, как будет работать наша программа, и выразим ее в псевдокоде:
main = Read list of directories and their sizes. Decide how to fit them on CD-Rs. Print solution.Звучит разумно? Я так и думал.
Давайте немного упростим нашу жизнь и пока предположим, что мы будем вычислять размеры каталогов где-то за пределами нашей программы (например, с помощью «
du -sb *») и читать эту информацию из stdin.
и более внимательно посмотрим на части решения.
Я думаю, вы можете использовать любой инструмент сжатия, который позволяет разбить архив
