Изменения

Перед решением основной задачи рассмотрим более простые.

<tex dpi = "200"> 1 \mid r_i,p_i = 1 \mid \sum f_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>

'''for''' <tex> i \leftarrow 2</tex> '''to''' <tex>n</tex> '''do'''

==Задача 2==

<tex dpi = "200"> 1 \mid \mid \sum w_i C_i</tex>

Входные данные для этой задачи: число работ <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>

<tex> C_0 \leftarrow 0</tex>

'''for''' <tex> i \leftarrow 1</tex> '''to''' <tex>n</tex> '''do'''