Изменения

Перейти к: навигация, поиск

1ripippmtnsumwu

2 байта убрано, 00:51, 6 июня 2016
м
Динамика
*Для любых <tex>t_u, t_v \in \Theta, u \leqslant v</tex> и для любого <tex>k \in [1, n]</tex> положим <tex>U_k(t_u, t_v) = \{J_i \mid i < k \wedge t_u <= r_i < t_v\}</tex> <tex>-</tex> множество работ, индекс которых меньше <tex>k</tex> и чьи <tex>r_i</tex> лежать в интервале <tex>[t_u, t_v).</tex>
*Пусть <tex>W_k(t_u, t_v, m)</tex> <tex>-</tex> максимальный вес множества работ <tex>Z \subset U_k(t_u, t_v), |Z| = m</tex> такой, что <tex>m \in (1, \dots ,n)</tex> и расписание от <tex>Z</tex> разрешимо и заканчивается до <tex>t_v</tex>. Если такое <tex>Z</tex> существует, будем говорить, что <tex>Z</tex> реализует <tex>W_k(t_u, t_v, m)</tex>. Если же такого <tex>Z</tex> нет, то <tex>W_k(t_u, t_v, m) = - \infty.</tex>
 
 
{{Лемма
32
правки

Навигация