748
правок
Изменения
→Описание алгоритма
\end{cases} .</tex>.
Тогда можно заметить, что <tex>x(d_i)=\sum\limits_{j=1}^m {l_j}</tex>, так как <tex>l_j=1</tex> если <tex>1 \leqslant j \leqslant m</tex> и <tex>h^S(d_i-m+j) < m</tex> или <tex>d_i-m+1 \leqslant d_i-m+j \leqslant d_i</tex> и <tex>h^S(d_i-m+j) < m</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)</tex> {{---}} минимальное значение целевой функции для расписания работ <tex>i, i+1, \ldots , n</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>f_i(k,k_1, \ldots , k_m)=\min\limits_{S: |S|=k, S \subseteq \{1, \ldots , i-1 \}}(\sum\limits_{j=i}^n {w_jU_j})</tex>.
