Условие:
Три актёра озвучивают мультфильм с пятью персонажами. Режиссер решил, что каждый актёр может озвучить не более двух персонажей. Баллы, показывающие, насколько актер соответствуют той или иной роли, занесены в следующую таблицу.
Распределить роли так, чтобы сумма баллов была максимальной. В ответе написать сумму баллов
Указание: добавить фиктивный персонаж и удвоить столбцы всех актеров
Получим матрицу соответствия:
Решение:
Умножением всех элементов на (-1) и затем сложением их с максимальным элементом матрицы (10) так, чтобы матрица не содержала бы отрицательных элементов:
во вновь полученной матрице в каждой строке будет как минимум один ноль.