Утилита для оптимального распределения файлов на несколько DVD?

У меня есть куча мультимедийных файлов, которые я хочу записать на DVD, но, поскольку каждый DVD занимает только 4,5 ГБ, я должен найти оптимальный способ организации файлов, чтобы использовать минимальное количество DVD-дисков (в противном случае на каждом из них остается свободное место). DVD можно легко сложить). Есть ли инструменты, которые помогут с этим?

Много лет назад была DOS-утилита, которая делала это с дискетами.

Попробуйте бесплатный DVD Span :

DVD Span - это инструмент резервного копирования для записи содержимого больших папок на несколько DVD. DVD Span может автоматически определять наилучшую организацию каждого диска, чтобы соответствовать максимальному количеству данных на минимальном количестве дисков. DVDSpan - отличный инструмент для резервного копирования вашей музыкальной коллекции, фотографий или даже всего жесткого диска на DVD. А поскольку он производит обычные DVD-диски (или компакт-диски), не требуется никакого специального программного обеспечения для чтения или восстановления ваших резервных копий.

Ах, проблема с рюкзаком . Я мог бы найти только один онлайн решатель для этого здесь . Ваш размер рюкзака будет 4,5 ГБ, а каждый пакет будет размером вашего файла. Вам нужно будет немного помассировать выходной сигнал, чтобы он соответствовал вашему конкретному применению, но он должен быть работоспособным. Это не будет работать очень быстро, потому что эта проблема сложная .

обзор

Ответ Джеффа Шаттока верен: он эквивалентен (или изоморфен, как пишут математики) задаче комбинаторной оптимизации, но он эквивалентен одномерной задаче упаковки бинов , а не проблеме ранцев .

К счастью для вас, у меня есть некоторый код, которым можно поделиться, чтобы решить эту проблему для вас или кого-либо еще с доступом к компьютеру Windows с установленной по крайней мере версией 3.5 .NET Framework.

Грубое решение

1. Сначала загрузите и установите LINQPad .

2. Во-вторых, скачайте запрос LINQPad, который я только что написал - вот linq (ha) в необработанный файл. Сохраните его как файл .linq и откройте его в LINQPad.

3. Измените параметры:

   Вот часть кода запроса 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размер вашего «мусорного ведра», например, 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";,

4. Запустите запрос, нажав F5или нажав кнопку « Выполнить» в левом верхнем углу вкладки запроса.

Полученные результаты

Код запроса будет rootFileFolderPathрекурсивно перечислять все файлы в папке, то есть он будет включать файлы также во всех подпапках.

Затем он создаст «корзины» для файлов, так что общий размер всех файлов в каждой корзине будет меньше или равен указанному размеру корзины.

На панели результатов LINQPad вы увидите два списка.

Первый список содержит все найденные файлы в порядке убывания размера.

Второй список - это корзины, созданные путем «упаковки файлов», со списком файлов и их размеров, а также оставшийся размер корзины.

Вот скриншот, показывающий второй список и первые две созданные корзины:

Беглый анализ

Согласно Википедии, алгоритм, который я использовал - стратегия First Fit Decreasing (FFD) - не должен быть слишком плохим; Википедия утверждает:

В 2007 году было доказано, что ограничение 11/9 OPT + 6/9 для FFD является жестким.

«ОПТ» относится к оптимальной стратегии (как нечто потенциально недоступное, а не какая-то конкретная фактическая стратегия).

Исходя из моих несколько нечетких воспоминаний о математических терминах, это должно означать, что стратегия FFD должна, в худшем случае, упаковывать элементы в ~ 1,22 раза больше ячеек, чем в оптимальной стратегии. Таким образом, эта стратегия может упаковать элементы в 5 корзин вместо 4. Я подозреваю, что ее производительность, вероятно, будет очень близка к оптимальной, за исключением определенных «патологических» размеров элементов.

В той же статье в Википедии также говорится, что существует «точный алгоритм» . Я могу решить реализовать это тоже. Сначала мне придется прочитать статью, в которой описан алгоритм.

Вы можете использовать любой инструмент сжатия, который позволяет разбить архив

Вы можете взять один из вариантов программы в путеводителе автостопом по Haskell , возможно, после проработки некоторой части этого урока; Учебное пособие написано с целью решения именно вашей проблемы распределения вещей на несколько дисков, в результате чего решение постепенно улучшается, о чем свидетельствует следующий отрывок из Главы 3 учебного пособия:

Уже достаточно предварительных экзаменов. давайте возьмем несколько компакт-дисков.

Как вы, возможно, уже поняли, наша проблема классическая. Это называется «проблема с рюкзаком» ( если вы еще не знаете, что это такое, запустите Google . Там более 100000 ссылок).

давайте начнем с жадного решения ...

Больше идей: связанный вопрос

Вот аналогичный вопрос (хотя и не тот же: его там не спрашивают об оптимизации), где вы можете найти более полезные решения / программы для вашей задачи (если они будут опубликованы):

• https://unix.stackexchange.com/q/10158/4319 - «Разбить большое дерево каталогов на куски указанного размера?»

Некоторые подсказки для понимания программирования в предлагаемом руководстве

В целом, код на Haskell довольно выразителен (поскольку Haskell - это язык для программирования на высоком уровне абстракции), и, следовательно, его легко понять.

Рассматривая код одного из решений, помните, что структура верхнего уровня программы, которую мы хотим написать, довольно проста, как изложено в главе 1 урока:

Теперь давайте немного подумаем о том, как будет работать наша программа, и выразим ее в псевдокоде:

main = Read list of directories and their sizes.
       Decide how to fit them on CD-Rs.
       Print solution.

Звучит разумно? Я так и думал.

Давайте немного упростим нашу жизнь и пока предположим, что мы будем вычислять размеры каталогов где-то за пределами нашей программы (например, с помощью " du -sb *") и читать эту информацию из stdin.

и более внимательно посмотрим на части решения.

Много лет назад я написал PHP-скрипт для решения этой задачи: https://bitbucket.org/borszczuk/php-backup-maker/

Также попробуйте Discfit, который выбирает файлы и каталоги для копирования на различные диски:

https://sourceforge.net/projects/discfit/