3622
правки
Изменения
→Алгоритм
q[i] = w[i] \ p[i]
L = {1, ... , n}
'''while''' L <tex> \ne </tex> {root} <font color=darkgreen>// пока в списке работ не останется только корень</font>
Найти работу j <tex> \in </tex> L с маскимальным значением q[j]
par = P[j]
w[i] += w[j]
p[i] += p[j]
q[i] = w[i] / w[j] <font color=darkgreen>// пересчитаем значения в вершине</font> P[j] = E[i] <font color=darkgreen>// предком работы j теперь будет последняя работа в <tex> \pi_i </tex></font> E[i] = E[j] <font color=darkgreen>// последней работой в <tex> \pi_i </tex> теперь будет последняя работа в <tex> \pi_j </tex></font>
J[i] = J[i] <tex> \cup </tex> J[j]
L = L \ {j}
Первой выберется работа с номером <tex> 5 </tex>. Она объединиться со своим родителем <tex> 2 </tex> и допишется в конец <tex> \pi_2 </tex>. Потом выберется работа <tex> 4 </tex>, потом <tex> \{2, 5\} </tex> и т. д. Процесс будет продолжаться, пока не останется одна вершина. Ответ {{---}} оптимальная последовательность работ {{---}} содержится в <tex> \pi_1 </tex>, который написан внутри последней вершины.
== Доказательство оптимальности алгоритма ==
{{Теорема
