748
правок
Изменения
→Описание алгоритма
\end{matrix} \right.</tex>.
Тогда можно заметить, что <tex>x(d_i)=\sum\limits_{j=1}^m {l_j}</tex>. Упростим Следовательно можно упростим исходное неравенство: <tex>m(d_i-m)-(km-\sum\limits_{j=1}^m {k_j})+\sum\limits_{j=1}^m {l_j} \geqslant m</tex> или <tex>m(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>.
