Изменения
Нет описания правки
=Простая задача =
Перед решением этой основной задачи рассмотрим более простуюпростые.
==Задача 1==
<tex dpi = "200"> 1 \mid r_i,p_i = 1 \mid \sum f_i</tex>
{{Задача
}}
==Описание алгоритма простой задачи1==
Нам нужно распределить <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>
==Псевдокод простой задачи1==
<tex>t_1 \leftarrow r_1 </tex>
'''for''' <tex> i \leftarrow 2</tex> '''to''' <tex>n</tex> '''do'''
<tex> t_i \leftarrow </tex> '''max'''<tex>(r_i, \ t_{i-1} - 1)</tex>
==Задача 2==
<tex dpi = "200"> 1 \mid \mid \sum w_i C_i</tex>
==Описание алгоритма простой задачи 2==
Входные данные для этой задачи: число работ <tex>n</tex> и два вектора <tex>p_i</tex>, <tex>w_i</tex> размера <tex>n</tex>.
Пусть в алгоритме задания перечислены так:
<tex>w_1/p_1 \geqslant w_2/p_2 \geqslant \ldots w_n/p_n</tex>
==Псевдокод простой задачи 2==
<tex> C_0 \leftarrow 0</tex>
'''for''' <tex> i \leftarrow 1</tex> '''to''' <tex>n</tex> '''do'''
<tex>C_i \leftarrow C_{i-1} + p_i</tex>
=Основная задача=
==Описание алгоритма основной задачи==
