264
правки
Изменения
→Пример
Поскольку любое задание выполняется за единицу времени, а все функции <tex>f_i</tex> являются неубывающими, то будет достаточно отсортировать работы по возрастанию времен появления и выполнять каждую работу как только она появится. Поскольку все <tex>r_i</tex> различны, то промежутки выполнения работ не будут пересекаться {{---}} расписание будет корректным.
== Примеры ===== Пример 1===Даны четыре задания. <tex>r_1 = 3, f_1 = 5t </tex> <tex>r_2 = 2, f_2 = t^2 </tex> <tex>r_3 = 4, f_3 = t + 4 </tex> <tex>r_4 = 1, f_4 = 2^t </tex> Отсортируем задания по неубыванию <tex>r_i</tex>, а дальше будем выполнять задания по мере появления. В полученном расписании работы будут идти в порядке <tex>4, 2, 1, 3</tex> и давать в ответе <tex>2^{1 + 1} + (2 + 1)^2 + 5(3 + 1) + (4 + 1) + 4 = 42 </tex>, что является оптимальным результатом.==Пример 2==
Рассмотрим простой пример.
Пусть у нас есть три задания, и каждое из них имеет время появления <tex>r_i = 0.</tex> Заданы функции <tex>f_i</tex>:
В результате будет выбрано расписание, в котором сначала будет идти третья, затем вторая, а затем первая работа.
== См. также ==
* [[Классификация задач]]
