1679
правок
Изменения
→Бинарный поиск по ответу
== Бинарный поиск по ответу ==
Этот способ часто подходит для задач, в которых надо минимизировать <tex> \sum w_i U_i </tex>. Важно помнить, что если требуется полиномиальное по <tex> n </tex> решение, оно не должно зависеть от логарифма ответа, но иногда ответ ограничен полиномом от <tex>n</tex> (в частности, в <tex> \sum U_i </tex>), и мы можем применить этот метод.
=== Примеры ===
==== O | p_ij = 1| Sum(U_i) ====Перенумеруем работы по возрастанию их дедлайнов, d_i то есть <tex> d_1 \le d_2 \le \dots d_n </tex>.{{Утверждение| statement=Если мы можем выполнить <tex> k </tex> каких- то работ, мы можем выполнить <tex> k </tex> последних работ.|proof=Действительно, если в допустимом расписании все периоды выполнения <tex> t_{iq} </tex> работы <tex> i </tex> заменить на периоды выполнения работы <tex> j > i </tex>, оно останется допустимым, так как <tex> t_{iq} \le d_i \le d_j </tex>.}}Таким образом, будем брать последние <tex> k </tex> работ и пытаться составить из них допустимое расписание (для этого известен полиномиальный алгоритм<ref>P. Brucker. Scheduling Algorithms (2006), 5th edition, p. 163 </ref>). Получили решение за <tex> O(\log n \cdot T_{exists}(n)) </tex>, где <tex> T_{exists} </tex> — время решения задачи <tex> O \mid p_{ij}===1, d_i \mid - </tex>.
== Жадное построение расписания ==
