317
правок
Изменения
→Специальные случаи
=== Специальные случаи ===
Если времена появления и дедлайны идут в одинаковом порядке, то есть <tex>r_1 \leqslant r_2 \leqslant \ldots \leqslant r_n</tex> и <tex>d_1 \leqslant d_2 \leqslant \ldots \leqslant d_n</tex>, то второй случай никогда не возникает. В этом случае, формула для вычисления <tex>C_j(r,w)</tex> может быть упрощена:
:<p>
<tex>C_{j}(r, w) = \min
\left \{\begin{array}{ll} C_{j - 1}(r, w) \\
\max \{r_j, C_{j - 1}(r, w - w_j) \} + p_j \end{array} \right.
</tex>
</p>
Либо, если мы примем <tex>C_{j}(w) = C_{j}(r_{\min}, w)</tex>, то:
:<p>
<tex>C_{j}(w) = \min
\left \{\begin{array}{ll} C_{j - 1}(w) \\
\max \{r_j, C_{j - 1}(w - w_j) \} + p_j \end{array} \right.
</tex>
</p>
Отсюда следует, что мы делаем <tex>O(nW)</tex> вычислений в этом случае, когда максимальный вес вычислимого множества <tex>w</tex> такой, что <tex>C_{n}(w)</tex> {{---}} конечно. В случае, если все веса одинаковы, но время уменьшается до <tex>O(n^2)</tex>.
Когда все времена появления работ равны нулю, рекурретная формула упрощается до
:<tex>C_j(w) = \min \{ C_{j - 1}(w), C_{j - 1}(w - w_{j}) + p_j\} </tex>
Отсюда следует альтернативное решение для задачи [[1sumwu|<tex>1 \mid\mid \sum w_j U_j</tex>]], которое работает за <tex>O(n\sum w_j)</tex>.
==Источники информации==
