37
правок
Изменения
Нет описания правки
Дано <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>. Теперь рассмотрим как решить её эффективнее.
==Описание алгоритма==
