Изменения
Нет описания правки
Дано <tex>n</tex> работ и один станок. Для каждой работы известно её время появления <tex>r_{i}</tex> и вес <tex>w_{i}</tex>. Время выполнения всех работ <tex>p_i</tex> равно <tex>1</tex>. Требуется выполнить все работы, чтобы значение <tex>\sum w_{i} C_{i}</tex> было минимальным, где <tex>C_{i}</tex> {{---}} время окончания работы.
}}
=Простая задача =
Перед решением этой задачи рассмотрим более простую.
Нам нужно распределить <tex>n</tex> работ в разное время. Если мы назначим время <tex>t</tex> для работы <tex>i</tex> то цена будет <tex>f_i(t + 1)</tex>. Так как нужно рассмотреть <tex>n</tex> временных промежутков, задача может быть решена за <tex>O(n^3)</tex>. Функция <tex>f_i</tex> монотонно неубывающая, тогда работы в расписании надо располагать как можно раньше для получения верного решения. <tex>n</tex> временных интервалов <tex>t_i</tex> для <tex>n</tex> работ могут быть получены с помощью следующего алгоритма, где предполагается что работы нумеруются так:
<tex> r_1 <= \leqslant r_2 <=... <= \leqslant \ldots \leqslant r_n</tex>
==Псевдокод простой задачи==
<tex>t_1 \leftarrow r_1 </tex>
'''FORfor''' <tex> i \leftarrow 2</tex> '''TOto''' <tex>n</tex> '''DOdo''' <tex> t_i \leftarrow </tex> '''MAXmax'''<tex>(r_i, \ t_{i-1} - 1)</tex>
=Основная задача=
==Описание алгоритма основной задачи==
Пусть <tex>time</tex> {{---}} текущий момент времени.<br/>
==Псевдокод основной задачи==
<tex> S \leftarrow \{1 \dots n\}</tex>
<tex> \mathtt{time } \leftarrow 0</tex> <tex> \mathtt{answer } \leftarrow 0</tex> '''WHILEwhile''' <tex> S \neq \varnothing </tex>
<tex> j \leftarrow null </tex>
'''IFif''' <tex> i \in S</tex> '''ANDand''' <tex> r_{i} \leq \mathtt{time}</tex> '''ANDand''' <tex>\max w_{i} </tex>
<tex> j \leftarrow i </tex>
'''IFif''' <tex>j \neq null </tex>
<tex> S \leftarrow S \setminus j</tex>
<tex> \mathtt{Answer } \leftarrow \mathtt{Answer } + \mathtt{time } \cdot w_{j}</tex> <tex> \mathtt{time++}</tex>
==Сложность алгоритма==
