Изменения
Нет описания правки
}}
==Общее Наивное решение==В общем случае, когда времена выполнения работ <tex>p_i</tex> могут быть сколь угодно большими или , например, дробными, данная задача может быть решена с помощью перебора. Будем перебирать все перестановки чисел от <tex>1</tex> до <tex>n</tex>, обозначающих номера заданий. При получении очередной перестановки просто будем пытаться выполнять задания в указанном порядке. Если значение <tex>\sum w_i U_i</tex>, полученное при данном расположении заданий, лучше, чем предыдущие результаты, то обновляем ответ. Данное решение будет работать за <tex>O(n \cdot n!)</tex>. ==Перебор с битовыми масками==
Далее широко будет использоваться следующий факт:
Далее мы сортируем задания из этого списка по времени неубывания дедлайнов, а те задания, что не попали в этот список, должны быть отправлены в конец расписания в любом порядке.
Далее проверяем полученное возможное расписание на корректность, и, в случае успеха, обновляем ответ.
Перебор всех масок может быть произведен за <tex>O(2 ^ n)</tex>, и <tex>O(n)</tex> на пересчет ответа. Таким образом, это решение будет работать за <tex>O(n \cdot 2^n)</tex>.
==Псевдополиномиальное решение==
Обозначим <tex>T = \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>0 \leqslant t \leqslant d_j </tex> и работа <tex>j</tex> успевает выполниться вовремя в расписании, соответствующем <tex>F_j(t)</tex>, то <tex>F_j(t) = F_{j- 1}(t - p_j)</tex>, иначе <tex>F_j(t) = F_{j- 1}(t) + w_i</tex>.
#Если <tex>t > d_j</tex>, то <tex>F_j(t) = F_{j}(d_j)</tex>, поскольку все работы с номерами <tex>j = 1, \ldots, j</tex>, законченные позже, чем <tex> d_j \geqslant \ldots \geqslant d_1 </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>
Для того, чтобы найти само расписание, по доказанной выше лемме, нам достаточно найти множество работ, которые будут выполнены с опозданием. Это может быть сделано следующим способом:
<tex>t = d_n</tex> <tex>L = \varnothing</tex>
'''for''' <tex>j = n</tex> '''downto''' <tex>1</tex>
<tex>t = \min(t, d_j)</tex>
