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>.
Пусть <tex>h^S</tex> {{---}} вектор соответствующий множеству <tex>S</tex> из задачи [[Opij1di|<tex> O \mid p_{i,j} = 1, d_i \mid - </tex>]]. Тогда, для добавления работы <tex>i</tex> в множество <tex>S</tex> должно выполняться неравенство: <tex>m\cdot (d_i-m)-(km-\sum\limits_{j=1}^m {h^S(d_i-m+j)})+x(d_i) \geqslant m</tex>, где <tex>k=|S|</tex> и <tex>x(d_i)</tex> {{---}} количество периодов времени <tex>t</tex> со свойствами: <tex>d_i-m+1 \leqslant t \leqslant d_i</tex> и <tex>h^S(t) < m</tex>. Чтобы проверить это неравенство, нам нужно посчитать <tex>m</tex> чисел <tex>h^S(t)</tex>, <tex>t=d_i-m+1, \ldots, d_i</tex>. Для этого определим переменные:
\end{matrix} \right.</tex>.
Тогда можно заметить, что <tex>x(d_i)=\sum\limits_{j=1}^m {l_j}</tex>. Следовательно можно упростим упростить исходное неравенство: <tex>m\cdot (d_i-m)-(km-\sum\limits_{j=1}^m {k_j})+\sum\limits_{j=1}^m {l_j} \geqslant m</tex> или <tex>m\cdot (d_i-m-k)+ \sum\limits_{j=1}^m {(k_j+l_j)} \geqslant m</tex>.
Для динамического программирования определим <tex>f_i(k,k_1 \ldots , k_m) = \min(\sum\limits_{j=i}^n {w_jU_j})</tex>, где <tex>k=|S|, S \subseteq \{1, \ldots , i-1\}</tex> и <tex>k_j=h^S(d_i-m+j)</tex> где <tex>j=1, \ldots , m</tex>.
