37
правок
Изменения
Нет описания правки
}}
==Простые Более простые варианты исходной задачи==
Перед решением основной задачи рассмотрим более простые.
===Задача Вариант 1===<tex dpi = "200"> 1 \mid p_i = 1\mid \sum C_i</tex>
Этот случай простейший. Ответом будет <tex>\sum_sum\limits_{k = 1}^n(k)</tex>, так как мы <tex>n</tex> раз сложим время окончания выполнения одной работы. В этом случае Воспользовавшись формулой суммы первых <tex>n</tex> членов арифметической прогрессии алгоритм <tex>S_n=\frac{a_1+a_n}2 \cdot n</tex> будет работает за <tex>O(n1)</tex>.
===Задача Вариант 2===<tex dpi = "200"> 1 \mid p_i = 1\mid \sum w_i C_i</tex>
<tex>f_{i}</tex> {{---}} монотонная функция времени окончания работы <tex>C_{i}</tex> для работ <tex>i = 1, 2, \ldots , n</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 \leqslant r_2 \leqslant \ldots \leqslant r_n</tex>
<tex> t_i \leftarrow </tex> '''max'''<tex>(r_i, \ t_{i-1} - 1)</tex>
Этот алгоритм работает за <tex>O(n \log n +n)</tex>
==Основная задача==
===Описание алгоритма===
'''while''' <tex> S \neq \varnothing </tex>
<tex> j \leftarrow null </tex>
'''if''' <tex> i \in S</tex> '''and''' <tex> r_{i} \leqslant \mathtt{time}</tex> '''and''' <tex>w_i \geqslant \max\limits_{j \in S, j = 1 \ldots n} w_j</tex>
<tex> j \leftarrow i </tex>
'''if''' <tex>j \neq null </tex>
==См. также==
* [[Классификация задач]]
* [[1ridipi11outtreesumwc|<tex>1 \mid outtree \mid \sum w_i C_i</tex>]]
* [[1ridipi1|<tex>1 | r_{i}, d_{i}, p_{i}=1 | -</tex>]]
