Изменения
Нет описания правки
==Алгоритм решения==
Пусть <tex> i_1, i_2, ... i_r </tex> последовательность работ, выполняемых на станке с номером <tex> j </tex>. Тогда вклад этих работ в целевую функцию будет равен <tex> p_{i1}\frac{r}{s_j} + p_{i2}\frac{r-1}{s_j}+...+p_{ir}\frac{1}{s_j} </tex>. Отсюда видно, что сумма оптимальна, когда последовательность <tex> p_{ij} </tex> не убывает.
Теперь введем неубывающую последовательность <tex> t_1, t_2 ... t_n </tex>, которая состоит из <tex> n </tex> маленьких элементов из множества <tex> \{\frac{1}{s_1}, \frac{1}{s_2} ... \frac{1}{s_m}, \frac{2}{s_1}, \frac{2}{s_2} ... \frac{2}{s_m}, \frac{3}{s_1} ... \}</tex>.Если <tex> t_i = \frac{k}{s_j} </tex>, то на <tex> j-том </tex> станке ==Псевдокод== for i=1 to m do Pj = f; wj=1/sj for i=1 to n do Find the largest index j of wj = min po m (w); pj = i+pj wj = wj+1/pj
