Изменения

Дано <tex>n</tex> работ и один станок. Для каждой работы известно её время появления <tex>r_{i}</tex> и вес <tex>w_{i}</tex>. Время выполнения всех работ <tex>p_i</tex> равно <tex>1</tex>.Требуется выполнить все работы, чтобы значение <tex>\sum w_{i} C_{i}</tex> было минимальным, где <tex>C_{i}</tex> {{---}} время окончания работы.

Это задание может быть сведено к более простому - Задаче о назначениях. По Перед решением этой причине можно решить задачу за <tex>O(n^3)</tex>. Теперь задачи рассмотрим как решить её эффективнееболее простую.

<tex dpi = "200"> 1 \mid r_i,p_i = 1 \mid \sum f_i</tex>{{Задача|definition=Дано <tex>n</tex> работ и один станок. Для каждой работы известно её время появления <tex>r_{i}</tex>. Время выполнения всех работ <tex>p_i</tex> равно <tex>1</tex>. Требуется выполнить все работы, чтобы значение <tex>\sum f_{i}</tex> было минимальным, где <tex>f_{i}</tex> {{---}} монотонная функция времени окончания работы <tex>C_{i}</tex>.}} ==Описание алгоритма простой задачи==Нам нужно распределить <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</tex> работ могут быть получены с помощью следующего алгоритма, где предполагается что рабочие места нумеруются так: <tex> r_1 <= r_2 <=... <= r_n</tex> ==Псевдокод простой задачи== <tex>t_1 \leftarrow r_1 </tex> '''FOR''' <tex> i \leftarrow 2</tex> '''TO''' <tex>n</tex> '''DO''' <tex> t_i \leftarrow </tex> '''MAX'''<tex>(r_i, \ t_{i-1} - 1)</tex> ==Описание алгоритмаосновной задачи==

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

==Псевдокодосновной задачи==