Изменения
Нет описания правки
==Псевдополиномиальное решение==
В ситуации, когда времена выполнения работ <tex>p_i</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>F_n(d_n)</tex>.
===Псевдокод===
Приведенный ниже алгоритм вычисляет <tex>F_j(t)</tex> для <tex>j = 0,\ldots, n </tex> и <tex>t = 0,\ldots, d_j </tex>. За <tex>p_{max}</tex> обозначим самое большое из времен выполнения заданий.
'''else'''
<tex> t = t - p_j </tex>
===Время работы===
Время работы приведенного выше алгоритма {{---}} <tex>O(n \sum\limits_{i=1}^n p_i)</tex>.
