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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Описание алгоритма)
(Удалено содержимое страницы)
 
Строка 1: Строка 1:
==Постановка задачи==
 
Рассмотрим задачу:
 
<ol>
 
<li>Дано <tex>n</tex> работ и один станок.</li>
 
<li>Для каждой работы известно её время появления <tex>r_{i}</tex> и вес <tex>w_{i}</tex>. Время выполнения всех работ равно <tex>1</tex>.</li>
 
</ol>
 
Требуется выполнить все работы, чтобы значение <tex>\sum w_{i}(c_{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}(time - r{i})</tex> максимально.</li>
 
<li> Выполняем <tex>j</tex> в момент времени <tex>time</tex> и увеличиваем <tex>time</tex> на один.
 
</ol>
 
 
==Доказательство корректности алгоритма==
 

Текущая версия на 20:21, 18 июня 2012