Каким способом проверить наличие уникального распределения в матрице?
Третий день бьюсь над решением:
Необходимо понять, существует ли такое распределение работников с набором навыков по работам, так чтобы все работы были выполнены.
Свел всё к задаче:
есть n человек и m навыков.
Считаем, что каждый человек может обладать от 1 до m навыков
нужно понять, существует ли хотя бы одно такое распределение людей, что все навыки будут покрыты.
Фактически, матрица m на n из единичек в случайных местах.
Считаем, что людей больше или равно числу работ, иначе очевидно, что такого распределения нет.
Самый простой случай:
1 1 1
1 0 0
1 0 0
три человека, один умеет всё, другие умеют одно и тоже. — Их недостаточно
Полагал искать ранг матрицы, чтобы он был не меньше числа навыков, но ранг матрицы
111
111
111
равен одному, а условиям распределения такой набор работников соответствует.
