Изменения

Перейти к: навигация, поиск

Участник:Qtr

46 байт убрано, 00:21, 5 июня 2016
Идея алгоритма
===Идея алгоритма===
Будем решать задачу рекурсивно. Разобьем множество работ на блоки, внутри которых работы могут выполняться непрерывно. После этого для каждого из блоков найдем работу, которую выгоднее всего выполнить последней, удалим работу из соответствующего блока и повторим разбиение на блоки для оставшихся работ. Пустые промежутки между подблоками, полученными из данного блока, заполним выбранной работой. Будем это делать то же самое для каждого из получившихся подблоков рекурсивно, пока они не опустеют. Как будет показано далее, данный алгоритм строит корректное и оптимальное расписание. Можно заметить, что если на каждом этапе будет получаться всего один блок, алгоритм выродится в [[Правило_Лаулера|алгоритм Лаулера]].
=== Препроцессинг ===
81
правка

Навигация