317
правок
Изменения
Нет описания правки
Выполнимое множество <tex>S</tex> является '''блоком''' (англ. ''block''), если работы из <tex>S</tex> обрабатываются непрерывно с начала и до конца, и <tex>S</tex> не может быть разделен на подмножества, расписания для которых не пересекаются, например, если <tex>C(S) = r(S)+ p(S)</tex> и <tex>S</tex> не является объединением <tex>S_{1}</tex> и <tex>S_{2}</tex> таких, что <tex>C(S_{1}) < r(S_{2})</tex>. Решим задачу <tex dpi>1 \mid r_i, pmtn \mid \sum w_{i}U_{i}</tex> методами динамического программирования.
Введем величину <tex>C_{i}(r, w) = \min \{C(S) \mid S \subseteq \{ 1 \ldots i \} </tex> {{---}} выполнимое<tex>; \wedge r(S) \geqslant r; \wedge w(S) \geqslant w \}</tex> и <tex>C_{i}(r, w) = \infty</tex>, если множеств, удовлетворяющих условиям, нет.
Максимальный вес выполнимого множества задается максимальным значением <tex>w</tex> такого, что <tex>C_{n}(r_{\min}, w</tex> конечно, где <tex>r_{\min} = \min\limits_{j = 1 \ldots n} r_{i}</tex>. Посчитаем значения <tex>C_{j}(r, w)</tex> за <tex>n</tex> итераций с начальными значениями
