обзор
Ответ Джеффа Шаттока верен: он эквивалентен (или изоморфен, как пишут математики) задаче комбинаторной оптимизации, но он эквивалентен одномерной задаче упаковки бинов, а не задаче о ранце.
К счастью для вас, у меня есть некоторый код, которым можно поделиться, который решит эту проблему для вас или любого другого, с доступом к компьютеру 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. Я подозреваю, что его производительность, вероятно, будет очень близка к оптимальной, за исключением определенных «патологических» размеров элементов.
В той же статье Википедии также говорится, что существует "точный алгоритм". Я могу решить реализовать это тоже. Сначала мне придется прочитать статью, в которой описан алгоритм.