Изменения

==Общее Наивное решение==В общем случае, когда времена выполнения работ <tex>p_i</tex> могут быть сколь угодно большими или , например, дробными, данная задача может быть решена с помощью перебора. Будем перебирать все перестановки чисел от <tex>1</tex> до <tex>n</tex>, обозначающих номера заданий. При получении очередной перестановки просто будем пытаться выполнять задания в указанном порядке. Если значение <tex>\sum \limits_{i=1}^n w_i U_i</tex>, полученное при данном расположении заданий, лучше, чем предыдущие результаты, то обновляем ответ. Данное решение будет работать за <tex> \mathcal{O}(n \cdot n!)</tex>. ==Перебор с битовыми масками== 

Применим В ситуации, когда времена выполнения работ <tex>p_i</tex> целочисленные, а значение <tex> \sum\limits_{i=1}^n p_i </tex> не очень большое, то для решения данной задачи можно применить [[Динамическое программирование|динамическое программирование]]. ===Описание алгоритма===

Для всех <tex>t = 0, 1, \ldots, T </tex> и <tex>j = 1, \ldots, n</tex> будем рассчитывать <tex>F_j(t)</tex> {{---}} значение целевой функции <tex>\sum w_i U_i</tex>, при условии, что были рассмотрены первые <tex>j</tex> работ и общее время выполнения тех из них, что будут закончены вовремя, не превышает времени <tex>t</tex>.

===Псевдокод===Приведенный ниже алгоритм вычисляет <tex>F_j(t)</tex> для <tex>j = 0,\ldots, n </tex> и <tex>t = 0,\ldots, d_j </tex>. * За <tex>p_{max}</tex> обозначим самое большое из времен выполнения заданий.* Значения <tex> F_j(t)</tex> будем хранить в массиве <tex>F[j][t]</tex>.* В массиве <tex>w[i] </tex> хранятся стоимости выполнения работ, в <tex>d[i] </tex> {{---}} дедлайны, а в <tex>p[i] </tex> {{---}} продолжительности выполнения. '''function''' <tex> \mathrm{getAnswer}(p : </tex> '''int'''<tex>\mathbf{[n]},</tex> <tex> w : </tex> '''int'''<tex>\mathbf{[n]},</tex> <tex> d : </tex> '''int'''<tex>\mathbf{[n]} ):</tex> '''int''' '''int''' <tex>T = 0 </tex> '''for''' <tex>i = 1 .. n</tex> <tex>T = T + p[i]</tex> '''int''' <tex>F[][]</tex> сортируем работы по неубыванию времен дедлайнов <tex>d[i]</tex> '''for''' <tex>t = -p_{max}</tex> '''to''' <tex>-1</tex> '''for''' <tex>j = 0</tex> '''to''' <tex>n</tex> <tex>F[j][t] = \infty</tex> '''for''' <tex>t = 0</tex> '''to''' <tex>T</tex> <tex>F[0][t] = 0</tex> '''for''' <tex>j = 1</tex> '''to''' <tex>n</tex> '''for''' <tex>t = 0</tex> '''to''' <tex>d[j]</tex> '''if''' <tex> F[j-1][t] + w[j] < F[j-1][t-p[j]] </tex> <tex> F[j][t] = F[j-1][t] + w[j] </tex> '''else''' <tex> F[j][t] = F[j-1][t-p[j]] </tex> '''for''' <tex>t = d[j] + 1</tex> '''to''' <tex>T</tex> <tex> F[j][t] = F[j][d[j]] </tex> '''return''' <tex> F[n][d[n]] </tex>

сортируем работы Для того, чтобы найти само расписание, по неубыванию времен дедлайнов доказанной выше лемме, нам достаточно найти множество работ <tex>d_iL</tex>, которые будут выполнены с опозданием. Это может быть сделано следующим способом: '''function''' <tex>t_1</tex> = <tex>r_1\mathrm{getLate}(F : </tex> '''forint''' <tex>t = -\mathbf{[n][p_{max}]},</tex> <tex> p : </tex> '''toint''' <tex>-1\mathbf{[n]},</tex> '''for''' <tex>j = 0w : </tex> '''toint''' <tex>\mathbf{[n]},</tex> F_j(t) = \infty '''for''' <tex>t = 0d : </tex> '''toint''' <tex>T\mathbf{[n]} ):</tex>'''set<int>''' F_0(t) = 0 '''forint''' <tex>j t = 1d[n]</tex> '''toset<int>''' <tex>nL = \varnothing</tex> '''for''' <tex>t j = 0n</tex> '''todownto''' <tex>d_j1</tex> <tex>t = \min(t, d[j])</tex> '''if''' <tex> F_{F[j][t] = F[j-1}(][t) ] + w_j < F_{w[j-1}(t-p_j) ] </tex> <tex> F_j(t) L = F_L \cup \{j-1\}(t) + w_j </tex>

<tex> F_j(t) = F_{j-1}(t-p_j) p[j] </tex> '''forreturn''' <tex>t = d_j + 1L</tex>Согласно лемме, само расписание будет состоять из работ, не попавших в <tex>L</tex> '''to''' , отсортированных по неубыванию <tex>Td_i</tex> и работ из <tex> F_j(t) = F_{j}(d_j) L</tex>, записанных в конец в любом порядке.

Для того, чтобы найти само расписание, по доказанной выше лемме, нам достаточно найти множество работ, которые будут выполнены с опозданием. Это может быть сделано следующим способом: t = d_n L = \varnothing=Время работы=== '''for''' В функции <tex>j = n\mathrm{getAnswer}</tex> '''downto''' пересчет динамики происходит за <tex>1\mathcal{O}(n T)</tex> , а функция <tex>t = \min(t, d_j)mathrm{getLate}</tex> '''if''' восстанавливает список просроченных работ за <tex> F_j(t) = F_\mathcal{j-1O}(tn) + w_j </tex> . Дальнейшее восстановление расписания происходит в худшем случае за <tex> L = L \cup \mathcal{jO}(n \} log n)</tex> </tex> '''else''' <tex> t = t - p_j </tex> ==Время работы== Время . Отсюда видно, что время работы приведенного выше алгоритма {{---}} <tex>\mathcal{O}\Big(n \sum\limits_{i=1}^n p_i\Big)</tex>.