264
правки
Изменения
Нет описания правки
Приведенный ниже алгоритм вычисляет <tex>F_j(t)</tex> для <tex>j = 0,\ldots, n </tex> и <tex>t = 0,\ldots, d_j </tex>.
* За <tex>p_{max}</tex> обозначим самое большое из времен выполнения заданий.
* Значения <tex> F_j(t)</tex> будем хранить в массиве <tex>F[j][t]</tex>.
* В массиве <tex>w[i] </tex> хранятся стоимости выполнения работ, в <tex>d[i] </tex> {{---}} дедлайны, а в <tex>p[i] </tex> {{---}} продолжительности выполнения.
'''function''' <tex> getAnswer(p : </tex> '''int''' <tex>[n],</tex> <tex> w : </tex> '''int''' <tex>[n],</tex> <tex> d : </tex> '''int''' <tex>[n] ):</tex> '''int'''
'''int''' <tex>T = 0 </tex>
'''for''' <tex>i = 1 .. n</tex>
<tex>T = T + p[i]</tex>
'''int''' <tex>F[][]</tex>
сортируем работы по неубыванию времен дедлайнов <tex>d[i]</tex>;
'''for''' <tex>t = -p_{max}</tex> '''to''' <tex>-1</tex>
'''for''' <tex>j = 0</tex> '''to''' <tex>n</tex>
<tex>F[j][t] = \infty</tex>
'''for''' <tex>t = 0</tex> '''to''' <tex>T</tex>
<tex>F[0][t] = 0</tex>
'''for''' <tex>j = 1</tex> '''to''' <tex>n</tex>
'''for''' <tex>t = 0</tex> '''to''' <tex>d[j]</tex>
'''if''' <tex> F[j-1][t] + w[j] < F[j-1][t-p[j]] </tex>
<tex> F[j][t] = F[j-1][t] + w[j] </tex>
'''else'''
<tex> F[j][t] = F[j-1][t-p[j]] </tex>
'''for''' <tex>t = d[j] + 1</tex> '''to''' <tex>T</tex>
<tex> F[j][t] = F[j][d[j]] </tex>
'''return''' <tex> F[n][d[n]] </tex>
'''else'''
<tex> F[j][t] = Ft - p[j-1][t-p_j] </tex> '''forreturn''' <tex>t = d_j + 1</tex> '''to''' <tex>T</tex> <tex> F[j][t] = F[j][d_j] L</tex>
===Время работы===
Время работы приведенного выше алгоритма {{---}} <tex>O\Big(n \sum\limits_{i=1}^n p_i\Big)</tex>.
