Погода: 1 °C
21.11−4...1пасмурно, без осадков
22.11−6...−2переменная облачность, небольшой снег
НГС.Форум /Компьютеры Интернет Связь / Программное обеспечение /

Оптимизация кучи файлов для записи на DVD

  • Подскажите софтинку:

    Есть куча файлов (>100), размером от 100 до 400 Мб (общий размер ~63 Гб), хочу все их записать на болванки, но так, что бы потерь свободного места было минимум. Файлы должны записываться целиком (не резать). Ну то есть чтобы программа оптимально распихала их по 14-15 (63Гб/4,5Гб=14) дискам.

    В идеале, что бы программа по подпапкам заданного размера разложила всю кучу файлов.


    Для тех кто не понял - пример:
    Есть файлы размером 1,2,3,4,5 усл. ед.. Есть диски размером 5 у.е.

    Если записывать "вручную" (по порядку) то надо 5 дисков
    1 диск - 1,2
    2 диск 3
    3 диск 4
    5 диск 5

    А если бы с искомой программой, то надо всего 3 диска

    1 диск - 2,3
    2 диск - 1,4
    3 диск - 5

    Ы?

  • Exсel.
    Но с вашей помощью - заводите список файлов с размерами и формулу под требуемые условия.

  • предлагаю вместо поиска проги начать запись болванок по известному вам алгоритму (как отчетливо видно из 1го поста ;)). 100 баллов, что записать их вручную быстрее, чем найти софтинку ))

  • Ручки и голова. Только так. Есть же еще идея объединения.... :спок: Если вы, ради экономии места, раскидаете два-три сериала по трем-четырем болваням.... перемешав их динамично. :безум: Это не по фен шую. :злорадство:

  • Ну собственно раскидал по порядку - получилось 15 дисков. Однако задача у меня уже вызвала чисто академический интерес:миг:

    Я уже изучил что такое комбинаторика:миг:А конкретно - сочетания.
    Хотел прикинуть алгоритм (в принципе могу и на VBA и на C пописать) - пришел к выводу, что везде приведены алгоритмы, осуществляющие весь перебор сочетаний.

    При выборке из n (166 - уточнил) файлов по k (12 файлов на диск в среднем) количество вариантов будет 166!/(12!*154!) - жуткое количество - 6,08356E+17.

    А учитывая рекурсивность алгоритмов - и памяти (стека) не хватит на организацию перебора всех вариантов.

    Испытания Excel'я показали, что он ограничен 32768'ю итерациями.

    К программистам в форум сунуться что ли:миг:

  • Тем кому интересно - весь мир на этим уже давно бьется.
    Задача называется - Задача о рюкзаке.

    Задача для максимально точного решения требует огромные вычислительные ресурсы.

    Есть упрощения - Жадный алгоритм.

    Собственно им я и воспользовался выполнив операции вручную.:миг:

  • В ответ на: Тем кому интересно - весь мир на этим уже давно бьется.
    Этого не знал, когда делал на Экселе.
    Про "жадный" почитал - не очень понял его суть.
    Мной был применён следующий алгоритм.

    Все файлы упорядочены по убванию размера (сверху вниз),
    набор идёт с наибольших размеров вниз, пока суммарный объём не превысит размер болвани (откат на один шаг), далее ищем оптимальный файл снизу вверх (тот после которого объём превысит размер болвани), результат - сумма нескольких больших и оптимального маленького (можно количество итераций увеличить, добивая остаток ещё меньшими файлами, но практического интереса не представляет).
    Далее всё повторяем - опять набираем большие файлы добиваем оптимальным(ми) маленькими.
    На такой практический (а не идеально-теоретический) алгоритм 32768 хватит, наверное.
    Ведь в данной задаче Optimum optimorum не так важен (разве что из академического интереса).

  • В ответ на:
    В ответ на: Тем кому интересно - весь мир на этим уже давно бьется.
    Про "жадный" почитал - не очень понял его суть.

    Все файлы упорядочены по убванию размера (сверху вниз),
    набор идёт с наибольших размеров вниз, пока суммарный объём не превысит размер болвани (откат на один шаг), далее ищем оптимальный файл снизу вверх (тот после которого объём превысит размер болвани), результат - сумма нескольких больших и оптимального маленького (можно количество итераций увеличить, добивая остаток ещё меньшими файлами, но практического интереса не представляет).
    Это и есть жадный алгоритм...:миг:От жадности начинаем с больших:миг:
    Во вложении найденная мной поделка немецких коллег.

    Stuckelung - Список значений (в моем случае длины файлов, в примере - суммы евров)
    Betrag - Сумма (Искомое значение, в моем случае размер DVD)
    Toleranz - Точность (сколько допустимо плюс/минус)
    Ergebnis - Оценка (для пересчета надо нажать F9, скрипт отключает автоматическое обновление)

    Полный перебор идет очень долго, однако если поставить точность не сильно маленькую - считает быстро.

  • В ответ на: Это и есть жадный алгоритм...:миг:От жадности начинаем с больших ;)
    Вот так всегда! Что не придумай - всё уже придумано до нас.:улыб:

  • Вот программа Ignition

Записей на странице:

Перейти в форум

Модераторы: