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

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

Версия 20:27, 18 июня 2012

Постановка задачи

Рассмотрим задачу:

  1. Дано [math]n[/math] работ и один станок.
  2. Для каждой работы известно её время появления [math]r_{i}[/math] и вес [math]w_{i}[/math]. Время выполнения всех работ [math]p_i[/math] равно [math]1[/math].

Требуется выполнить все работы, чтобы значение [math]\sum w_{i}(c_{i} - p_{i} - r_{i})[/math] было минимальным.

Описание алгоритма

Пусть [math]time[/math] — текущий момент времени.
Для каждого очередного значения [math]time[/math], которое изменяется от [math]0[/math] до времени окончания последний работы, будем:

  1. Выбирать работу [math]j[/math] из множества невыполненных работ, у которой [math]r_{i} \le time[/math] и значение [math]w_{i}(time - r_{i})[/math] максимально.
  2. Если мы смогли найти работу [math]j[/math], то выполняем её в момент времени [math]time[/math]
  3. Увеличиваем [math]time[/math] на один.

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