264
правки
Изменения
→Решение
отсортиртировать работы по неубыванию времен дедлайнов <tex>d_i</tex>
<tex>t_1</tex> = <tex>r_1</tex>
'''for''' <tex> t \in \{ = -p_{max} \ldots </tex> '''to''' <tex>-1 \} </tex> '''for''' <tex> j \in \{ = 0 \ldots </tex> '''to''' <tex>n \} </tex>
F_j(t) = \infty
'''for''' <tex> t \in \{ = 0 \ldots </tex> '''to''' <tex>T \} </tex>
F_0(t) = 0
'''for''' <tex> j \in \{ 0 \ldots = 1</tex> '''to''' <tex>n \} </tex> '''begin''' '''for''' <tex> t \in \{ = 0 \ldots </tex> '''to''' <tex>d_j \} </tex> '''if''' <tex> F_{j-1} + w_j < F_{j-1}(t-p_j) </tex> '''then'''
<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 \in \{ d_{j= d_j +1} \ldots </tex> '''to''' <tex>T \} </tex>
<tex> F_j(t) = F_{j}(d_j) </tex>
'''end'''
t = d_n
L = \varnothing
'''for''' <tex>j = n</tex> '''downto''' <tex>1</tex>
'''begin'''
<tex>t = \min(t, d_j)</tex>
'''if''' <tex> F_j(t) = F_{j-1}(t) + w_j </tex>
<tex> L = L \cup \{j\} </tex> </tex>
'''else'''
<tex> t = t - p_j </tex>
'''end'''
==Доказательство корректности и оптимальности==
