4446
правок
Задача присваивания: различия между версиями
Материал из WEGA
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 12: | Строка 12: | ||
<math>\forall y \in Y \; \; \; \ell(y) = 0</math> | <math>\forall y \in Y \; \; \; \ell(y) = 0</math> | ||
<math>\forall x \in X \; \; \; \ell(x) = max_{y \in Y} \; w(x, y).</math> | <math>\forall x \in X \; \; \; \ell(x) = max_{y \in Y} \; w(x, y).</math> | ||
| Строка 27: | Строка 25: | ||
Действительно, заметим, что сумма меток является верхней границей веса паросочетания с максимальным весом. Алгоритм последовательно находит паросочетание и допустимую разметку, такие, что вес паросочетания оказывается равен сумме всех меток. | |||
