Изменения

==Общее Наивное решение==В общем случае, когда времена выполнения работ <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>i</tex> равен <tex>1</tex>, то это задание успеет должно быть записано в список заданий, которые, возможно, успеют выполниться, а если бит равен <tex>0</tex> {{---}} то не успеет.Далее, согласно доказанной лемме, мы должны выписать все сортируем заданияиз этого списка по времени неубывания дедлайнов, которыеа те задания, по нашему предположениючто не попали в этот список, могут должны быть выполнены без опоздания в начало расписания в порядке возрастания дедлайнов <tex>d_i</tex>, а оставшиеся записать отправлены в конец расписания в любом порядке.Далее проверяем полученное возможное расписание на корректность, и, в случае успеха, обновляем ответ. Перебор всех масок может быть произведен за <tex>\mathcal{O}(2 ^ n)</tex>, и <tex>\mathcal{O}(n)</tex> на пересчет ответа. Таким образом, это решение будет работать за <tex>\mathcal{O}(n \cdot 2^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>.