264
правки
Изменения
Нет описания правки
Будем перебирать все перестановки чисел от <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>\mathcal{O}(2 ^ n)</tex>, и <tex>\mathcal{O}(n)</tex> на пересчет ответа. Таким образом, это решение будет работать за <tex>\mathcal{O}(n \cdot 2^n)</tex>.
==Псевдополиномиальное решение==
===Время работы===
В функции <tex>\mathrm{getAnswer}</tex> пересчет динамики происходит за <tex>\mathcal{O}(n T)</tex>, а функция <tex>\mathrm{getLate}</tex> восстанавливает список просроченных работ за <tex>\mathcal{O}(n)</tex>. Дальнейшее восстановление расписания происходит в худшем случае за <tex>\mathcal{O}(n \log n)</tex>. Отсюда видно, что время работы приведенного выше алгоритма {{---}} <tex>\mathcal{O}\Big(n \sum\limits_{i=1}^n p_i\Big)</tex>.
==См. также ==
