|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Andrey Tarasevich 2:5020/400 06 Oct 2001 06:50:03
To : Rick Hustle
Subject : Re: Распределение файлов по CD
--------------------------------------------------------------------------------
Rick Hustle wrote:
>
> Есть такая задачка:
> Есть N файлов, (разных размеров < ёмкости CD болванки) и k CD болванок
> (фиксированного размера). Hадо наиболее оптимальным образом "распихать" файлы
> по болванкам. Под оптимумом подразумевается что-бы как можно большее кол-во
> болванок было забито с свободным местом <=10Mb.
>
> Интересем алгоритм решения этой задачки отличный от "тупого" перебора
> комбинаций. Т.к. уже при кол-ве файлов полядка > 12 задача становится ОЧЕHЬ
> долгорешаемой.
> ...
Задача похожа на классический одномерный раскрой, только вот твой
вариант выглядит слегка перегруженным дополнительными условиями.
Пусть Vm - объем одного CD в мегабайтах, а Vf - суммарный объем всех
файлов в мегабайтах.
Очевидно, что количество CD, которое придется использовать: не менее L =
Vf/Vm и не более H = Vf/(Vm - 10) (L округляется вверх, H - вниз).
Если H < L, то задача не имеет решения.
В противном случае роль числа k зависит от того, где оно лежит по
отношению к диапазону [L, H].
Если k < L, задача не имеет решения.
В противном случае кол-во использованных CD бкдет лежать в диапазоне [L,
min(k, H)]
Правильно я понимаю условие?
Best regards,
АHдрей.
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
