748
правок
Изменения
м
→Описание алгоритма
}}
==Описание алгоритма==
Для решения этой задачи, мы должны найти множество <tex>S</tex>работ, что которые успеваем выполнить до дедлайна. Значит нам надо минимизировать: <tex>\sum\limits_{i \notin S} {w_{i} U_{i}}</tex> минимальна. Будем решать эту задачу с помощью [[Динамическое_программирование|динамического программирования ]] с использованием утверждений из решения задачи [[Opij1di|<tex> O \mid p_{i,j} = 1, d_i \mid - </tex>]].
Рассмотрим работы в порядке неубывания дедлайнов: <tex>d_{1} \leqslant d_{2} \leqslant \ldots \leqslant d_{n}</tex>. Пусть мы нашли решение для работ <tex>1, 2, \ldots, i-1</tex>. Очевидно, что <tex>S \subseteq \{1, \ldots i-1\}</tex>.
