Вопрос (или с больной головы на здоровую)

Есть балванка на 700М
Есть файлы:
ааа 400М
ввв 400М
ссс 400М
еее 300М
ххх 300М
ооо 300М

Если я их буду записывать на диски подряд, то я потрачу 5 дисков
Если я их буду записывать на диски так: ааа+еее, ввв+ххх, ссс+ооо то я потрачу 3 диска

Вопрос: если программа или формула/макро в excel-е которая мне поможет правильно/оптимально скомпановать файлы?

Советы типа "заархивируй с опцией -v700K" или "используй backup утилиту" не годятся файлы ложны быть в оригинальном виде.

Спасибо, математики.

формула простая ( к математике имеет маленькое отношение)

1. Берется самый большой файл из имеющихся.
2. Проверятется лезет ли он на диск
3. Если даю брется следующий файл и go to 1
4. Если не лезет, то берется следуюший, меньший по размеру файл и go to 1

Приведённая выше формула не всегда работает

Хотя я тоже начинаю с больших файлов. Обычно просто сваливаю все файлы в одну кучу, в FAR-е сортирую по размеру и начинаю выделять начиная с самых больших, добивая остатки мелкими. Набранные файлы копирую в другую директорию, откуда из все скопом и пишу.

Да, формула имеет мало отношения к математике. Потому, что она в общем случае не верна. Я потом подберу пример. Сейчас времени нет.

Насколько я помню, это эквивалентно какой-то NP-complete задаче. Так что решения не будет Пользуйтесь методами типа генетических алгоритмов.

Впрочем, если речь идет не о математике, а о распределении файлов по дискам, то полный перебор - вполне реальный метод.

Кстати, алгоритмы типа приведенного BRMAIL'ом принято называть "жадными" (greedy) алгоритмами. Они редко дают оптимальные результаты.

НУ, по жизни, я тоже пользуюсь. BRMAIL-оским методом, но просто не верю, что это задачка не решена и не воплощена в код.
И, к стати, сортирую тоже в FAR-е.
Обожаю FAR-овский встроенный редактор! Кто-нибудь, что-нибуд подобное c GUI знает?

This post has been edited by Ruz on 17-09-2004, 03:29

Что такое NP-полная задача вы в курсе?

Нет, просвети пожалуйста.
Но решение то должно быть диски то жечь надо.

This post has been edited by Ruz on 17-09-2004, 04:21

Эта задача легко решается полным перебором. Число файлов ограничено, размер болванки известен. Надо всего лишь разложить на меньшее число "кучек", минимизировав остаток. Лень писать программу, руками обычно получается не сильно хуже. У меня никогда на 10 дисков инфы писать сразу не набирается, так как пишу на ДВД , а на пару дисков, руками быстрее, чем программу запустить.

Согласен.
Но вот после двух аварий HDD решил всю коллекцию аудио книг перенести но DVD (от греха подальше) А это 230Гб, думал, что если подойти с научной точки зрения , то болванку другую сэкономлю.
Но жизнь показала обратное. «Хвостик» на последнем DVD сводит к 0 все ухищрения на первых NN дисках.

This post has been edited by Ruz on 17-09-2004, 04:29

А чего-бы народу не побаловаться? Запости размеры сюда и мы все попробуем "кто меньше"

а чЁ постить, заходи на ftp, там все размеры и названия, я там даже решение оставил.
(а шутка мне понравилась, не знаю посему, но понравилась)

Не совсем понял, где живет ФТП со списком и размерами файлов, но если речь идет о 230 гигах, то это явно многие сотни файлов. Полный перебор может ээ... оказаться долгим занятием Если кто хорошо помнит комбинаторику, то пусть посчитает точное количество вариантов, но слова "факториал" и "многие сотни элементов", как правило дают вполне астрономические числа...

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

obaldin
А кто говорил что будет легко? . Вариантов для 230 гигов будет много, очень много. Поэтому легче руками, особенно если много мелких файлов.