3622
правки
Изменения
м
→Время работы
Ответ на задачу будет находиться в <tex>f_{1} (0, 0, \ldots , 0)</tex>.
==Пример работы==
Пусть <tex>m = 2</tex> и <tex>n = 3</tex>.
{| class="wikitable" style="width:5cm" border=1
|+
|-align="center" bgcolor=#EEEEFF
! номер работы || дедлайн || вес
|-align="center" bgcolor=#FFFFFF
| 1 || 2 || 7
|-align="center" bgcolor=#FFFFFF
| 2 || 2 || 6
|-align="center" bgcolor=#FFFFFF
| 3 || 2 || 5
|}
Для такой задачи получится таблица для функции <tex>f</tex>:
{| class="wikitable" style="width:20cm" border=1
|+
|-aling="center" bgcolor=#EEEEFF
! <tex>k</tex> || <tex>k_1</tex> || <tex>k_2</tex> || <tex>f_{4} (k, k_1, k_2)</tex> || <tex>f_{3} (k, k_1, k_2)</tex> || <tex>f_{2} (k, k_1, k_2)</tex> || <tex>f_{1} (k, k_1, k_2)</tex>
|-align="center" bgcolor=#FFFFFF
| 0 || 0 || 0 || 0 || 0 || 0 || 5
|-align="center" bgcolor=#FFFFFF
| 0 || 0 || 1 || 0 || 0 || 0 || 0
|-align="center" bgcolor=#FFFFFF
| 0 || 0 || 2 || 0 || 0 || 0 || 0
|-align="center" bgcolor=#FFFFFF
| 0 || 1 || 0 || 0 || 0 || 0 || 0
|-align="center" bgcolor=#FFFFFF
| 0 || 1 || 1 || 0 || 0 || 0 || 0
|-align="center" bgcolor=#FFFFFF
| 0 || 1 || 2 || 0 || 0 || 0 || 0
|-align="center" bgcolor=#FFFFFF
| 0 || 2 || 0 || 0 || 0 || 0 || 0
|-align="center" bgcolor=#FFFFFF
| 0 || 2 || 1 || 0 || 0 || 0 || 0
|-align="center" bgcolor=#FFFFFF
| 0 || 2 || 2 || 0 || 0 || 0 || 0
|-align="center" bgcolor=#FFFFFF
| 1 || 0 || 0 || 0 || 5 || 11 || 7
|-align="center" bgcolor=#FFFFFF
| 1 || 0 || 1 || 0 || 5 || 11 || 7
|-align="center" bgcolor=#FFFFFF
| 1 || 0 || 2 || 0 || 5 || 0 || 0
|-align="center" bgcolor=#FFFFFF
| 1 || 1 || 0 || 0 || 5 || 11 || 7
|-align="center" bgcolor=#FFFFFF
| 1 || 1 || 1 || 0 || 0 || 5 || 7
|-align="center" bgcolor=#FFFFFF
| 1 || 1 || 2 || 0 || 0 || 0 || 0
|-align="center" bgcolor=#FFFFFF
| 1 || 2 || 0 || 0 || 5 || 0 || 0
|-align="center" bgcolor=#FFFFFF
| 1 || 2 || 1 || 0 || 0 || 0 || 0
|-align="center" bgcolor=#FFFFFF
| 1 || 2 || 2 || 0 || 0 || 0 || 0
|-align="center" bgcolor=#FFFFFF
| 2 || 0 || 0 || 0 || 5 || 0 || 0
|-align="center" bgcolor=#FFFFFF
| 2 || 0 || 1 || 0 || 5 || 0 || 0
|-align="center" bgcolor=#FFFFFF
| 2 || 0 || 2 || 0 || 5 || 0 || 0
|-align="center" bgcolor=#FFFFFF
| 2 || 1 || 0 || 0 || 5 || 0 || 0
|-align="center" bgcolor=#FFFFFF
| 2 || 1 || 1 || 0 || 5 || 0 || 0
|-align="center" bgcolor=#FFFFFF
| 2 || 1 || 2 || 0 || 5 || 0 || 0
|-align="center" bgcolor=#FFFFFF
| 2 || 2 || 0 || 0 || 5 || 0 || 0
|-align="center" bgcolor=#FFFFFF
| 2 || 2 || 1 || 0 || 5 || 0 || 0
|-align="center" bgcolor=#FFFFFF
| 2 || 2 || 2 || 0 || 5 || 0 || 0
|}
Действительно, в <tex>f_1 (0, 0, 0)</tex> записано <tex>5</tex>, что является минимальным значением целевой функции.
==Время работы==
Для определения времени работы алгоритма надо заметить, что <tex>i = 0, \ldots , n</tex>, <tex> k = 0, \ldots , n</tex> и <tex>k_j = 0, \ldots m</tex> где <tex>j = 1, \ldots , m</tex>. Из рекуррентной формулы очевидно, что для подсчета одного значения <tex>f_{i} (k, k_{1}, \ldots , k_{m})</tex> нужно <tex>O(m)</tex> времени. Значит , алгоритм работает за <tex>O(n^2 m^{m + 1})</tex>.
==См. также==
* [[Opij1di|<tex> O \mid p_{i,j} = 1, d_i \mid - </tex>]]* [[Opi1sumu|<tex>O \mid p_{iji, j} = 1 \mid \sum U_i</tex>]]* [[1pi1sumwu|<tex>1 \mid p_{i} = 1 \mid \sum w_{i}U_{i}</tex>]]
==Источники информации==
