748
правок
Изменения
→Описание алгоритма
<tex>f_i(k,k_1 \ldots , k_m)=\left\{\begin{matrix}
f_{i+1}(k,k_{1+p},k_{2+p}, \ldots, k_{m+p})+w_i, & m\cdot (d_i-m-k)+ \sum\limits_{j=1}^m {(k_j+l_j)} < m (1)\\\min(f_{i+1}(k,k_{1+p},k_{2+p}, \ldots ,k_{m+p})+w_i ; f_{i+1}(k+1,k_{1+p}+l_{1+p},k_{2+p}+l_{2+p}, \ldots ,k_{m+p}+l_{m+p})), & m\cdot (d_i-m-k)+ \sum\limits_{j=1}^m {(k_j+l_j)} \geqslant m(2)\\
\end{matrix} \right.</tex>
и начальное условие: <tex>f_{n+1}(k,k_1,\ldots ,k_m)=0 </tex> для <tex>k,k_1,\ldots ,k_m = 0,1,\ldots ,m</tex>.
Если выполняется неравенство <tex>(1)</tex>, то мы не можем добавить работу <tex>i</tex> в множество <tex>S</tex> и поэтому <tex>f_i(k,k_1 \ldots , k_m) = f_{i+1}(k,k_{1+p},k_{2+p}, \ldots, k_{m+p})+w_i</tex>.
Если выполняется неравенство <tex>(2)</tex>, тогда мы может добавить работу <tex>i</tex> в множество <tex>S</tex> или не добавлять. Если мы добавим работу <tex>i</tex>, то <tex>f_i(k,k_1 \ldots , k_m) = f_{i+1}(k+1,k_{1+p}+l_{1+p},k_{2+p}+l_{2+p}, \ldots ,k_{m+p}+l_{m+p}) (3)</tex>. Если мы не добавим работу <tex>i</tex>, то по аналогии с первым случаем <tex>f_i(k,k_1 \ldots , k_m) = f_{i+1}(k,k_{1+p},k_{2+p}, \ldots, k_{m+p})+w_i (4)</tex>. Так как <tex>f_i(k,k_1 \ldots , k_m) = \min(\sum\limits_{j=i}^n {w_jU_j})</tex>, то нам надо взять минимум из значений <tex>(3)</tex> и <tex>(4)</tex>.
Ответ на задачу будет находиться в <tex>f_1(0,0,\ldots,0)</tex>.
