|
|
| Строка 1: |
Строка 1: |
| − | ==Постановка задачи==
| |
| − | Рассмотрим задачу:
| |
| − | <ol>
| |
| − | <li>Дано <tex>n</tex> работ и один станок.</li>
| |
| − | <li>Для каждой работы известно её время появления <tex>r_{i}</tex> и вес <tex>w_{i}</tex>. Время выполнения всех работ <tex>p_i</tex> равно <tex>1</tex>.</li>
| |
| − | </ol>
| |
| − | Требуется выполнить все работы, чтобы значение <tex>\sum w_{i}(c_{i} - p_{i} - r_{i})</tex> было минимальным.
| |
| | | | |
| − | ==Описание алгоритма==
| |
| − | Пусть <tex>time</tex> {{---}} текущий момент времени.<br/>
| |
| − | Для каждого очередного значения <tex>time</tex>, которое изменяется от <tex>0</tex> до времени окончания последней работы, будем:
| |
| − | <ol>
| |
| − | <li> Выбирать работу <tex>j</tex> из множества невыполненных работ, у которой <tex>r_{i} \le time</tex>, а значение <tex>w_{i}</tex> максимально.</li>
| |
| − | <li> Если мы смогли найти работу <tex>j</tex>, то выполняем её в момент времени <tex>time</tex> и удаляем из множества невыполненных работ.</li>
| |
| − | <li> Увеличиваем <tex>time</tex> на один.</li>
| |
| − | </ol>
| |
| − |
| |
| − | ==Доказательство корректности алгоритма==
| |
| − | {{Теорема
| |
| − | |statement=
| |
| − | Расписание, построенное данным алгоритмом, является корректным и оптимальным.
| |
| − | |proof=
| |
| − | Доказательство будем вести от противного.<br/>
| |
| − | Рассмотрим расписание <tex>S_{1}</tex>, полученное после выполнения нашего алгоритма, и оптимальное расписание <tex>S_{2}</tex>.<br/>
| |
| − | Возьмём первый момент времени <tex>t_{1}</tex>, когда расписания различаются. Пусть в этот момент времени в <tex>S_{1}</tex>, будет выполняться работа с весом <tex>w_{1}</tex>, а в <tex>S_{2}</tex> {{---}} работа с весом <tex>w_{2}</tex>.<br/>
| |
| − | Это первый момент, в котором расписания отличаются, значит в <tex>S_{2}</tex> работа с весом <tex>w_{1}</tex> выполнится в момент времени <tex>t_{2} > t_{1}</tex>.<br/>
| |
| − | Поменяем местами работы с весами <tex>w_{1}</tex> и <tex>w_{2}</tex> в <tex>S_{2}</tex> и полуим расписание <tex>S_{3}</tex>. Это возможно, потому что время появления этих работ не меньше <tex>t_{1}</tex>.<br/>
| |
| − | При такой перестановке ответы на задачу для <tex>S_{2}</tex> и <tex>S_{3}</tex> будут отличаться на
| |
| − | <ul><tex>(t_{1} - r_{2})w_{2} + (t_{2} - r_{1})w_{1} - ((t_{1} - r_{1})w_{1} + (t_{2} - r_{2})w_{2}) = t_{1}(w_{2} - w_{1}) + t_{2}(w_{1} - w_{2}) = (t_{1} - t_{2})(w_{2} - w_{1})</tex></ul>
| |
| − | Первая скобка отрицательная: <tex>t_{1} < t_{2}</tex>. Вторая скобка тоже отрицательная из того, что в <tex>S_{1}</tex> работа с весом <tex>w_1</tex> выполняется раньше, значит её вес должен быть больше <tex>w_2</tex>.<br/>
| |
| − | Итого имеем, что ответ для <tex>S_{2}</tex> больше, чем ответ для <tex>S_{3}</tex>. Следовательно расписание <tex>S_2</tex> неоптимальное. Получили противоречие. Значит не существует такого момента времени, когда расписание <tex>S_{1}</tex> отличается от оптимального. Следовательно мы доказали, что оно оптимальное.
| |
| − | }}
| |
| − |
| |
| − | ==Псевдокод==
| |
| − | <tex> S \leftarrow \{1 \dots n\}</tex>
| |
| − | <tex> time \leftarrow 0</tex>
| |
| − | <tex> answer \leftarrow 0</tex>
| |
| − | while <tex> S \neq \varnothing </tex>
| |
| − | <tex> j \leftarrow i : (\max \limits_{i \in S, r_{i} \leq time} w_{i})</tex>
| |
| − | if <tex>j \neq null </tex>
| |
| − | <tex> S \leftarrow S \setminus j</tex>
| |
| − | <tex> Answer \leftarrow Answer + (time - r_{j})w_{j}</tex>
| |
| − | <tex> time++</tex>
| |
| − |
| |
| − | ==Сложность алгоритма==
| |
| − | Множество <tex>S</tex> станет пустым не позже, чем через <tex>n + \max r_{i}</tex> шагов цикла. Определить максимум в множестве можно за время <tex>O(\log n)</tex>, используя , например, очередь с приоритетами. Значит общее время работы алгоритма <tex>O((n + \max r_{i})\log n)</tex>
| |
