1632
правки
Изменения
м
[[Файл{| class="wikitable" style="float:right; margin-left: 10px;"|-! ! style="width:50px;"|<tex>t = 1</tex>! style="width:50px;"|<tex>2</tex>! style="width:30px;"|<tex>...</tex>! style="width:50px;"|<tex>d_i - m + 1</tex>! style="width:50px;"|<tex>d_i - m + 2</tex>! style="width:Shd230px;"|<tex>...jpg</tex>! style="width:50px;"|<tex>d_i - 1</tex>! style="width:50px;"|<tex>d_i</tex>|-! style="width:50px;"|<tex>m = 1</tex>| | | | style="text-align:center;"|<tex>i</tex>| | |300px|thumb|right-! style="width:50px;"|<tex>2</tex>| | | | | style="text-align:center;"|<tex>i</tex>| |||-! style="width:50px;"|<tex>\vdots</tex>| | | | | | style="text-align:center;"|<tex>\ddots</tex>|||-! style="width:50px;"|<tex>m - 1</tex>| | | | || | style="text-align:center;"|<tex>i</tex>||-! style="width:50px;"|<tex>m</tex>| | | | || | | style="text-align:center;"|<tex>i</tex>|-! colspan="9"|РисТабл. 1. Работа <tex>i</tex> назначена на интервалы <tex>d_i - m + 1 \ldots d_i</tex>.]]|}
rollbackEdits.php mass rollback
== Описание алгоритма ==
=== Идея ===
Заметим, что если <tex>d_i < m</tex>, то очевидно, что <tex>C_i > d_i</tex>, следовательно, расписания не существует. Поэтому будем полагать, что <tex>m \leqslant d_i</tex> для <tex>i = 1 \ldots n</tex>.
Определим <tex>h(t)</tex> {{---}} количество работ во временном интервале <tex>t</tex>.
'''void''' checkExistenceOfSchedule('''int[]'''* <tex>d</tex>):
<tex>T = \max\{d_i \mid i = 1 \ldots n\}</tex>
'''for''' <tex>t = 1</tex> '''to''' <tex>T</tex>
<tex>h(k_0) = m</tex>
'''if''' <tex>h(1) \leqslant m</tex>
'''return''''' true''
'''else'''
'''return''''' false''
''Замечание:'' если расписание существует, то оно может быть вычислено данным алгоритмом, если добавить в цикл (1) функцию, отвечающую за добавление работы <tex>i</tex> на момент <tex>j</tex> в расписании для соответствующей машины и в цикл (2) функцию, отвечающую за перемещение работы, которой нет во временном интервале <tex>k_0 - 1</tex>, но которая есть в <tex>k_0</tex>, на момент <tex>k_0 - 1</tex> в той же машине (этот шаг будет обоснован далее в доказательстве корректности).
