|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Rick Hustle 2:5030/961.111 07 Oct 2001 02:32:32
To : Andrey Tarasevich
Subject : Re: Распределение файлов по CD
--------------------------------------------------------------------------------
Отвечаю на ваше письмо от 06.10.2001, тогда писал(а) Andrey Tarasevich
к Rick Hustle, а было тогда на часах 6:50:03.
>> Есть такая задачка:
>> Есть N файлов, (разных размеров < ёмкости CD болванки) и k CD болванок
>> (фиксированного размера). Hадо наиболее оптимальным образом "распихать"
>> файлы по болванкам. Под оптимумом подразумевается что-бы как можно большее
>> кол-во болванок было забито с свободным местом <=10Mb.
>> Интересем алгоритм решения этой задачки отличный от "тупого" перебора
>> комбинаций. Т.к. уже при кол-ве файлов полядка > 12 задача становится ОЧЕHЬ
>> долгорешаемой.
>> ...
AT> Задача похожа на классический одномерный раскрой, только вот твой
AT> вариант выглядит слегка перегруженным дополнительными условиями.
AT> Пусть Vm - объем одного CD в мегабайтах, а Vf - суммарный объем всех
AT> файлов в мегабайтах.
AT> Очевидно, что количество CD, которое придется использовать: не менее L =
AT> Vf/Vm и не более H = Vf/(Vm - 10) (L округляется вверх, H - вниз).
AT> Если H < L, то задача не имеет решения.
AT> В противном случае роль числа k зависит от того, где оно лежит по
AT> отношению к диапазону [L, H].
AT> Если k < L, задача не имеет решения.
AT> В противном случае кол-во использованных CD бкдет лежать в диапазоне [L,
AT> min(k, H)]
AT> Правильно я понимаю условие?
Всё правильно за исключеним:
H=Vf/(Vm - 10) может оказаться не верхней границей кол-ва CD.
Пример: Размер CD 700 Мб. И есть 3 файла по 400Мб. Распихаются только на 3
CD, а Vf/(Vm - 10)=1.73 Округляем вверх получаем 2.
Rick.
---
* Origin: Хорошо в Сибири летом - целый месяц снега нету... (2:5030/961.111)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
