317
правок
Изменения
→Конечная формула
Если <tex>r(S'') = r</tex>, то пусть <tex>S' \subseteq S''</tex> будет блоком <tex>S''</tex> таким, что <tex>r(S') = r</tex>. Можно предположить, что <tex>C(S') = C_{j - 1}(r, w(S'))</tex>. Следовательно, общее количество сделанной работы из <tex>S'</tex> в интервале <tex>[r_j, r']</tex> будет равно
:<tex>\max \{ 0, C_{j - 1}(r, w(S')) - r_j \} </tex>.
Пусть <tex>r''</tex> будет наименьшей датой появления, меньшей или равной <tex>C_{j - 1}(r, w(S'))</tex>. Тогда общее количество сделанной работы в <tex>S'' \setminus S' </tex> в интервале <tex>[r_j, r']</tex> будет равно <tex>P_{j - 1}(r'', r', w'' - w(S'))</tex>. Следовательно, общее количество сделанной работы в <tex>S''</tex> в интервале <tex>[r_j, r']</tex> будет равно
:<tex>\max \{ 0, C_{j - 1}(r, w(S')) - r_j\} + P_{j - 1}(r'', r', w'' - w(S'))</tex>.
Правая часть выражения должна быть минимальной для множеств <tex>S', S'' \setminus S'</tex> и <tex>r(S') = r, C(S') \leqslant r( S'' \setminus S') = r'', w(S') + w( S'' \setminus S') = w''</tex>. Собирая все вместе, получим формулу
:<p>
<tex>P_{j - 1}(r, r', w'') = \min
\left \{\begin{array}{ll} P_{j - 1}(r^+, r', w'') \\
\min\limits_{0 < w' \leqslant w''} \{ \max \{ 0, C_{j - 1}(r, w') - r_j \} + P_{j - 1}(r'', r', w'' - w')\} \end{array} \right.
</tex>
</p>
С начальными значениями
: <tex>P_{j - 1}(r, r', 0) = 0</tex> для <tex>j = 1 \ldots n</tex>
: <tex>P_{0}(r, r', w'') = \infty</tex> для <tex>w'' > 0\ldots n</tex>
=== Ассимптотика ===
