Назначьте N задач N людям, чтобы минимизировать общее время

Есть N человек и N рабочих мест. Дан массив arr[] размера N*N , где (arr[0], arr[1], . . ., arr[N-1]) обозначает время, затраченное первым человеком на выполнение (1- ^й , 2- ^й , . . ., N ^-й ) работы соответственно и аналогично от приб[N] до приб[2*N -1] для второго и так далее для остальных лиц. Задача состоит в том, чтобы поручить каждую задачу только одному человеку и только одну задачу каждому человеку так, чтобы общее время, затрачиваемое всеми людьми на выполнение всех работ, было минимальным.

Примеры:

Input: N = 2, Arr[] = {3, 5, 10, 1}
Output: 4
Explanation: The first person takes times 3 and 5 for jobs 1 and 2 respectively. The second person takes times 10 and 1 for jobs 1 and 2 respectively. We can see that the optimal assignment will be to give job 1 to person 1 and job 2 to person 2 for a total for 3 + 1 = 4.

Input: N = 3, Arr[] = {2, 1, 2, 9, 8, 1, 1, 1, 1}
Output: 3 
Explanation: The optimal arrangement would be to assign job 1 to person 3, job 2 to person 1 and job 3 to person 2.

Наивный подход: основной способ решения проблемы заключается в следующем:

The problem can be solved by checking all the possible combinations formed and check the minimum time taken to complete the N jobs.

Следуйте инструкциям, чтобы решить эту проблему:

• Используя следующую перестановку, мы можем сгенерировать все возможные перестановки массива рабочих, которые получат задание.
• После получения каждой перестановки мы будем перебирать N заданий и вычислять время, необходимое для выполнения задачи.
• После подсчета всего затраченного времени мы выведем минимальное время, необходимое для выполнения N заданий из всех перестановок.

Ниже приведена реализация описанного выше подхода.

Временная сложность: O(N! * N) Для вычисления всех перестановок требуется N! факториальное время, и в каждой перестановке мы будем вычислять время, необходимое для выполнения N заданий. Итак, нам нужно пройти N элементов в каждой комбинации.
Вспомогательное пространство: O(N ² ), поскольку нам дано время, затрачиваемое на каждую работу, выполненную каждым человеком. Таким образом, имеется N человек и N рабочих мест, поэтому требуется сложность O(N ² ).

Эффективный подход: для решения проблемы следуйте следующей идее:

We will be using The Hungarian algorithm, aka Munkres assignment algorithm, utilizes the following theorem for polynomial runtime complexity and guaranteed optimal

Следуйте инструкциям, чтобы решить эту проблему:

1. Создайте матрицу затрат. Матрица затрат представляет собой квадратную матрицу, в которой указано N человек для каждой стоимости работы.
2. Если число добавляется ко всем элементам любой строки или столбца матрицы затрат или вычитается из них, то оптимальное назначение для результирующей матрицы затрат является также оптимальным назначением для исходной матрицы затрат.
3. Мы уменьшаем нашу исходную матрицу затрат, чтобы она содержала нули, используя приведенную выше теорему. Мы пытаемся назначать агентам задачи так, чтобы каждый агент выполнял только одну задачу, а штраф в каждом случае был равен нулю.
4. Для каждой строки матрицы найдите наименьший элемент и вычтите его из каждого элемента в этой строке.
5. Сделайте то же самое (как в шаге 2) для всех столбцов.
6. Закройте все нули в матрице, используя минимальное количество горизонтальных и вертикальных линий.
7. Тест на оптимальность: если минимальное количество покрывающих строк равно N , оптимальное назначение возможно, и мы закончили.

Ниже приведена реализация описанного выше подхода.

Временная сложность: O(N ² )
Вспомогательное пространство: O(N ² )