748
правок
Изменения
→Описание алгоритма
Тогда можно заметить, что <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_</tex> {{j=---}} минимальное значение целевой функции для расписания работ <tex>i, i}^+1, \ldots , n {w_jU_j})</tex>, позволяющее выполнить работы из множества <tex>S</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>.
Пусть <tex>p=d_{i+1}-d_i</tex>, тогда определим рекуррентное выражение для <tex>f_i(k,k_1 \ldots , k_m)</tex>:
