32
правки
Изменения
→Решение
#<tex>U_k(t_u, t_v) = \{J_i \mid i < k ; t_u <= r_i < t_v\};</tex>
#<tex>W_k(t_u, t_v, m)</tex> - максимальный вес <tex>Z \subset U_k(t_u, t_v), |Z| = m</tex> такой, что <tex>m \in (1, \dots ,n)</tex> и <tex>JPS</tex> от <tex>Z</tex> разрешимо и заканчивается до <tex>t_v</tex>. Если такого <tex>Z</tex> не существует, то <tex>W_k(t_u, t_v, m) = - \infty.</tex>}}
{{Лемма
|statement=
<tex>\forall t_u, t_v \in \Theta, u <= v, \forall k \in (1, \dots ,n), \forall m \in (1, \dots ,n):</tex>
* <tex>r_k \notin [t_u, t_v) \Rightarrow W_k(t_u, t_v, m) = W_{k-1}(t_u, t_v, m);</tex>
* Иначе <tex>W_k(t_u, t_v, m) = max(W_{k-1}(t_u, t_v, m), W'_k)</tex>
<tex>W'_k = w_k + max(W_{k-1}(t_u, t_x, m_1) + W_{k-1}(t_x, t_y, m_2) + W_{k-1}(t_y, t_v, m_3))</tex>
|proof=
}}
== См. также ==
