Изменения

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

1ripippmtnsumwu

87 байт добавлено, 00:18, 6 июня 2016
Псевдокод
=== Псевдокод ===
'''int''' Solve('''int[]''' d, '''int[]''' r, '''int[]''' w) Отсортировать работы по <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 = 2</tex> '''to''' <tex>n</tex> '''for''' <tex>m = 1</tex> '''to''' <tex>n</tex> '''foreach''' <tex>t_u, t_v \in \Theta \mid t_u \leqslant t_v</tex> '''if''' <tex>p r_k \leqslant (not\minin [t_u, t_v)</tex> <tex>W_k (d_1t_u,t_v, m)= W_{k -\max1} (r_1t_u, t_v,t_u)m)</tex> '''else''' <tex>W'_k = </tex> Подсчитать <tex>W'_k</tex> по формуле из леммы <tex>W_1W_k (t_u, t_v, m) = \max(W_{k - 1} (t_u, t_v, m), W'_k\}) = w_1</tex>
'''for''' <tex>k = 2</tex> '''to''' <tex>n</tex> '''for''' <tex>m = 1</tex> '''to''' <tex>n</tex> '''foreach''' <tex>t_u, t_v \in \Theta \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>\max\limits_{i \in [1, \dots, n]}(W_n(\min\limits_{t \in \Theta} (t - p), \max\limits_{t \in \Theta} (t), i))</tex>
=== Оценка алгоритма ===
32
правки

Навигация