1pi=1wirisumwi(ci - pi -ri) — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Описание алгоритма)
(Удалено содержимое страницы)
 
Строка 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>
 

Текущая версия на 00:52, 19 июня 2012