32
правки
Изменения
→Динамика
Исходя из двух неравенств доказанных выше, можно получить требуемое равенство <tex>W_k(t_u, t_v, m) = \max(W_{k-1}(t_u, t_v, m), W'_k).</tex> Лемма доказана.
}}
=== Псевдокод ===
Отсортировать работы по <tex>d_i</tex>
<tex>fill(W, -\infty)</tex>
'''foreach''' <tex>t_u, t_v \in \Theta \mid t_u \leqslant t_v</tex>
'''if''' <tex>p \leqslant (\min(d_1,t_v)-\max(r_1,t_u))</tex>
<tex>W_1(t_u, t_v, 1) = w_1</tex>
'''for''' <tex>k = 1</tex> '''to''' <tex>n</tex>
'''for''' <tex>m = 1</tex> '''to''' <tex>n</tex>
'''foreach''' <tex>t_u, t_v \in \Theta, m \in [1, n] \mid t_u \leqslant t_v</tex>
'''if''' <tex>r_k \not\in [t_u, t_v)</tex>
<tex>W_k (t_u, t_v, m) \leftarrow W_{k - 1} (t_u, t_v, m)</tex>
'''else'''
<tex>W'_k \leftarrow </tex> Подсчитать <tex>W'_k</tex> по формуле из леммы
<tex>W_k (t_u, t_v, m) \leftarrow \max(W_{k - 1} (t_u, t_v, m), W'_k\})</tex>
'''return''' <tex>W_n(\min\limits_{t \in \Theta} (t - p), \max\limits_{t \in \Theta} (t), n)</tex>
== См. также ==
