748
правок
Изменения
→Описание алгоритма
1 & j \in \{1 , \ldots , m\}\text{; } k_j < m \\
0 & \text{otherwise} \\
\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)=\begin{cases}
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 \text{ } (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 \text{ }(2)\\
\end{cases}</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}) \text{ } (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 \text{ } (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>.
