|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Andrey Dashkovsky 2:5002/46.4 04 Oct 2001 16:59:33
To : Rick Hustle
Subject : Re: Распределение файлов по CD
--------------------------------------------------------------------------------
01 Окт 01 20:48, you wrote to all:
RH> Есть такая задачка:
RH> Есть N файлов, (разных размеров < ёмкости CD болванки) и k CD
RH> болванок (фиксированного размера). Hадо наиболее оптимальным образом
RH> "распихать" файлы по
RH> болванкам. Под оптимумом подразумевается что-бы как можно большее
RH> кол-во
RH> болванок было забито с свободным местом <=10Mb.
RH> Интересем алгоритм решения этой задачки отличный от "тупого" перебора
RH> комбинаций. Т.к. уже при кол-ве файлов полядка > 12 задача становится
RH> ОЧЕHЬ долгорешаемой.
Если отсортируешь по возрастанию, и будешь на CD сначала самые большие пихать,
потом с конца перебирать + нормальное отсечение - не так уж и долго. Другими
словами есть 8 8 7 6 4 4 3 3 3 1 , и примеру размер 18 получаем
8 8 = 16, запоминаем, выбрасываем 8 на 7
8 7 3 = 18, остаётся 8 6 4 4 3 3 1
8 6 4 = 18, остаётся 4 3 3 1 = 11
Правда такой вариант может не самое оптимальное брать, однако довольно
эффективное всяки. К сожалению не могу красивый тест придумать, но нечно
подобное я как-то рисовал, работало нормально.
Andrey
... а то эта NTя - пpямо квест какой-то, можно сутками пpоходить ...
--- GoldED+/386 1.1.4.7
* Origin: Всёфигня кроме пчёл,хотя пчёлы,еслиподумать,тоже фигня (2:5002/46.4)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
