37
правок
Изменения
Нет описания правки
}}
Перед решением основной задачи рассмотрим более простые.
==Задача 1==
<tex dpi = "200"> 1 \mid p_i = 1\mid \sum C_i</tex>
'''Описание алгоритма'''
Входные данные для этой задачи: число работ <tex>n</tex>
Этот случай простейший. Для верного выполнения просто выставим работы по порядку, тогда ответом будет <tex>n</tex>, так как мы <tex>n</tex> раз сложим время выполнения одной работы, которое в нашем случае единица.
==Задача 2==
<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'''
<tex> t_i \leftarrow </tex> '''max'''<tex>(r_i, \ t_{i-1} - 1)</tex>
==Задача 3==
<tex dpi = "200"> 1 \mid r_j,p_j = 1 p \mid \sum f_j</tex>
Вес всех работ <tex>w_i \geqslant 0</tex>
<tex>f_i - f_j</tex> неубывающая функция для <tex>i, j = 1, 2, \ldots, n</tex> при <tex>i < j </tex>
<tex>\sum w_i C_i</tex> являются функцией <tex>f_j(C_j)</tex>, так что по факту решаем задачу <tex>1 \mid r_j,p_j = 1 p \mid \sum w_i C_i </tex>=='''Описание алгоритма задачи <tex>1 \mid r_j,p_j = 1 \mid \sum f_j</tex>=='''
Пусть перед началом алгоритма работы пронумерованы в соответствии с свойствами для функций <tex>f_1, f_2, \ldots, f_n</tex>
<tex>T</tex> это множество {<tex>r_j + lp \mid j = 1, 2, \ldots, n; l = 0, 1, \ldots, n-1 </tex>}
<tex>F_k'''Calculate''' (s,e)</tex> это <tex>F_nmin(F_{k-1}(s,t_k)+F_{k-1}(t_k + p, e)+f_k(t_k + p) \mid t_k \in T, max(s, r_k) \leqslant t_k \leqslant e-p)</tex> просто вычисляет функцию для поданных значений. '''Псевдокод'''
'''for all''' <tex>s, e \in T \ with \ s \leqslant e</tex> '''do'''
<tex>F_0(s,e) \leftarrow 0</tex>
F_k(s,e) \leftarrow
\begin{cases}
F_{k-1}(s,e) \ if \ r_k \notin [s - p,e);\\ F_k'(s,e) \ otherwiseoverwise;
\end{cases}
</tex>
'''CalculateВычислить''' <tex>F_n($$ \min_{i=1}^n (r_i) $$, max_{t \in T}(t+p) )</tex>=Основная задача===Описание алгоритма основной задачи==
Пусть <tex>time</tex> {{---}} текущий момент времени.<br/>
Для каждого очередного значения <tex>time</tex>, которое изменяется от <tex>0</tex> до времени окончания последней работы, будем:
</ol>
==Доказательство корректности алгоритма основной задачи==
{{Теорема
|statement=
}}
==Псевдокод основной задачи==
<tex> S \leftarrow \{1 \dots n\}</tex>
<tex> \mathtt{time} \leftarrow 0</tex>
