Изменения

=Простая задача =Более простые варианты исходной задачи== 

==Задача =Вариант 1===<tex dpi = "200"> 1 \mid r_i,p_i = 1 \mid \sum f_iC_i</tex>{{Задача|definition=Дано <tex>n</tex> работ и один станокЭтот случай простейший. Для каждой работы известно её время появления Ответом будет <tex>r_\sum\limits_{ik = 1}^n k</tex>. Время выполнения всех работ , так как мы <tex>p_in</tex> равно раз сложим время окончания выполнения одной работы. Воспользовавшись формулой суммы первых <tex>1n</tex>. Требуется выполнить все работы, чтобы значение членов арифметической прогрессии алгоритм <tex>S_n=\sum f_dfrac{ia_1+a_n}2 \cdot n</tex> было минимальным, где будет работает за <tex>f_{i}O(1)</tex> {{---}} монотонная функция времени окончания , но если нужно вывести и само расписание, время работы будет <tex>C_{i}</tex> для работ <tex>i = 1, 2, ..., O(n)</tex>.}}

==Описание алгоритма простой задачи 1=Вариант 2===Нам нужно распределить <tex>n</tex> работ в разное время. Если мы назначим время <tex>t</tex> для работы <tex>i</tex> то цена будет <tex>f_i(t + 1)</tex>. Так как нужно рассмотреть <tex>n</tex> временных промежутков, задача может быть решена за <tex>O(n^3)</tex>. Функция <tex>f_i</tex> монотонно неубывающая, тогда работы в расписании надо располагать как можно раньше для получения верного решения. <tex>n</tex> временных интервалов <tex>t_i</tex> для <tex>n\mid p_i = 1\mid \sum w_i C_i</tex> работ могут быть получены с помощью следующего алгоритма, где предполагается что работы нумеруются так:

Для верного выполнения просто выставим работы по порядку невозрастания весов, тогда ответом будет <tex> r_1 \leqslant r_2 sum\leqslant \ldots \leqslant r_n</tex> =limits_{i =Псевдокод простой задачи 1== <tex>t_1 \leftarrow r_1 }^nw_i C_i</tex> '''for''' <tex> i \leftarrow 2</tex> '''to''' , так как мы <tex>n</tex> '''do''' <tex> t_i \leftarrow </tex> '''max'''раз сложим время окончания выполнения одной работы (которое в нашем случае <tex>(r_i, \ t_C_{i-1} - +1)</tex>) домноженное на вес этой работы. Данный алгоритм корректен по [[Задача_о_минимуме/максимуме_скалярного_произведения|теореме о минимуме/максимуме скалярного произведения]], так как мы сопоставляем две последовательности, подходящие под условия теоремы.

==Задача 2==Так как [[Сортировка|сортировка]] весов занимает <tex dpi = "200"> 1 \mid \mid O(n \sum w_i C_i</tex>==Описание алгоритма простой задачи 2==Входные данные для этой задачи: число работ <tex>log n)</tex> и два вектора <tex>p_i</tex>время, то асимптотика времени работы алгорита равна <tex>w_i</tex> размера <tex>O(n + n \log n)</tex>.Пусть в алгоритме задания перечислены так:

<tex>w_1/p_1 \geqslant w_2/p_2 \geqslant \ldots w_n/p_n</tex> ==Псевдокод простой задачи 2Основная задача== <tex> C_0 \leftarrow 0</tex> '''for''' <tex> i \leftarrow 1</tex> '''to''' <tex>n</tex> '''do''' <tex>C_i \leftarrow C_{i-1} + p_i</tex>=Основная задача===Описание алгоритма основной задачи===

<li> Выбирать работу <tex>j</tex> из множества невыполненных работ, у которой <tex>r_{i} \le leqslant time</tex>, а значение <tex>w_{i}</tex> максимально.</li>

===Доказательство корректности алгоритма основной задачи===

===Псевдокод основной задачи=== ====Реализация 1==== <tex> S \leftarrow \{1 \dots ldots n\}</tex>

'''if''' <tex> i \in S</tex> '''and''' <tex> r_{i} \leq leqslant \mathtt{time}</tex> '''and''' <tex>w_i \geqslant \max w_\limits_{ij \in S, j = 1 \ldots n} w_j</tex>

==Сложность алгоритма==Множество <tex>S</tex> станет пустым не позже, чем через <tex>n + \max \limits_{i = 1 \ldots n} r_{i}</tex> шагов цикла. Определить максимум в множестве можно за время <tex>O(\log n)</tex>, используя , например, [[:Категория:Приоритетные_очереди|очередь с приоритетами]]. Значит общее время работы алгоритма <tex>O((n + \max \limits_{i = 1 \ldots n} r_{i})\log n)</tex> ====Реализация 2====* <tex>\mathtt{Q}</tex> {{---}} обычная [[Очередь | очередь]], в которой работы изначально располагаются в отсортированном по <tex>r_i</tex> порядке,* <tex>\mathtt{P}</tex> {{---}} [[Приоритетные очереди | приоритетная очередь]] по максимуму.  <tex> \mathtt{time} \leftarrow 1</tex> <tex> \mathtt{answer} \leftarrow 0</tex> '''while''' <tex>\mathtt{Q} \neq \varnothing </tex> '''and''' <tex>\mathtt{P} \neq \varnothing </tex> '''if''' <tex>\mathtt{Q} \neq \varnothing </tex> <tex> j \leftarrow \mathtt{Q.head()}</tex> '''if''' <tex>\mathtt{time} < r_j</tex> <tex>\mathtt{time} \leftarrow r_j</tex> '''while''' <tex> \mathtt{time} \geqslant r_j</tex> <tex>\mathtt{P.insert}(w_j)</tex> <tex>\mathtt{Q.pop()}</tex> '''if''' <tex>\mathtt{Q} = \varnothing </tex> '''break''' '''else''' <tex> j \leftarrow \mathtt{Q.head()}</tex> <tex> \mathtt{Answer} \leftarrow \mathtt{Answer} + \mathtt{time} \cdot \mathtt{P.extractMax()} </tex> <tex> \mathtt{time}\texttt{++}</tex> Данная реализация имеет идею, аналогичную предыдущей: сначала обрабатывать работу с максимальным весом среди всех доступных.В начале работы сортируются по <tex>r_i</tex>, из очереди <tex>\mathtt{Q}</tex> достаётся каждая работа, причём ровно один раз, аналогично для очереди <tex>\mathtt{P}</tex>, поэтому итоговая асимптотика времени работы алгоритма составляет <tex>O(n \log n)</tex>.

== Источники информации ==* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 19 - 20* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 38-39* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 84 - 85* Лазарев А.А., Мусатова Е.Г., Кварацхелия А.Г., Гафаров Е.Р. Пособие по теории расписаний.