3622
правки
Изменения
м
→Время работы
Приведенный ниже алгоритм вычисляет оптимальную последовательность работ <tex>\pi</tex> для множества работ <tex>I = \{i_1, i_2,\ldots, i_r\}</tex> в начальный момент времени <tex>t</tex>.
'''function''' <tex>\mathrm{sequence}</tex> (<tex>t</tex>: '''int''', <tex>I</tex>: '''int[]'''): '''int[]'''
'''if''' <tex>I = \varnothing</tex>
'''return''' <tex>\varnothing</tex>
Рассмотрим 2 случая:
# '''<tex>C_j</tex> <tex>\leqslant d_j</tex>. '''
#:Тогда <tex>C_j = \min\{d_j, C_j\} \leqslant d'_j \leqslant \max\{d_j, C_j\} = d_j </tex>, из чего следует <tex> w_j\max\{0, C_j ~$-$~ d_j\} = w_j\max\{0, C_j ~$-$~ d'_j\} = 0.</tex>
#:<tex>C_j \leqslant d'_j \leqslant d_j </tex>, и, учитывая <tex>C'_j \leqslant d'_j, d'_j C'_j \leqslant d_j</tex> и <tex>d_j \leqslant C'_j,</tex> получаем, что <tex>w_j \max\{0, C'_j ~$-$~ d_j\} = w_j\max\{0, C'_j ~$-$~ d'_j\} - w_j \max\{0, \min\{C'_j, d'_j\} ~$-$~ d_j\} </tex>.
#:<tex>A_j = 0 </tex>,
#:<tex>B_j = w_j \max\{0, \min\{C'_j, d_j \} ~$-$~d'_j\} </tex>;
# '''<tex>C_j \geqslant d_j</tex>. '''
#:Тогда <tex>d_j = \min\{d_j, C_j\} \leqslant d'_j \leqslant \max\{d_j, C_j\} = C_j </tex>, из чего следует <tex> w_j\max\{0, C_j ~$-$~ d_j\} = w_j\max\{0, C_j ~$-$~ d'_j\} + w_j(d'_j ~$-$~ d_j). </tex>
#:<tex>d_j \leqslant d'_j \leqslant C_j</tex> , получаем, что <tex>w_j \max\{0, C'_j ~$-$~ d_j\} = w_j\max\{0, C'_j ~$-$~ d'_j\} + w_j \max\{0, \min\{C'_j, d'_j\} ~$-$~ d_j\} </tex>.
Пускай все времена выполнения работ различны. Тогда все множества работ, используемые в качестве аргументов рекурсивного вызова функции можно представить в виде <tex>\langle i, j, k \rangle : \{ v \mid i \leqslant v \leqslant j \wedge p_v < p_k\}</tex>, <tex> i, j, k \in \{1, 2, \ldots, n\}</tex>.
У нас максимум <tex> p = \sum\limits_{i=1}^n p_i</tex> различных значений <tex>t</tex>. Значит, мы вызовем <tex> \mathrm{sequence}(t,I)}</tex> в худшем случае <tex>\mathcal{O}(n^3p)</tex> раз. Более того, для фиксированного <tex>k</tex> все значения <tex>\max\{p_v \mid v \in I_{ijk}\}</tex> для <tex>i, j = 1,\ldots, n,</tex> <tex>i < j</tex> могут быть сосчитаны за <tex>\mathcal{O}(n^2)</tex>.
Таким образом, мы получаем алгоритм, работающий за <tex>\mathcal{O}(n^3p)</tex> или <tex>\mathcal{O}(n^4p_{max})</tex>, где <tex>p_{max} = \max\limits_{i=1}^n p_i</tex>.
