Как выбрать матричные элементы с наименьшей суммой при условии, что их строки и столбцы отличаются друг от друга?

Question

Я хочу выбрать элемент из каждой строки при условии, что их столбцы отличаются друг от друга. Сумма элементов также должна быть как можно ниже.

9 2 7 8
6 4 3 7
5 8 1 8
7 6 9 4

например, ответ этой матрицы: 2 (из строки 1) + 6 (из строки 2) + 1 (из строки 3 ) + 4 (из строки 4)

я должен сохранить индексы выбранных элементов.

У вас есть идея? Поделись, пожалуйста. Спасибо

Answer 1

Этот алгоритм должен работать:

1. с учетом матрицы N x N
2. получить самый маленький элемент в матрице, запомните его
3. удалить его строка и столбец из матрицы, поэтому матрица становится N-1 x N-1
4. , пока матрица не пуста, go до шага 2

Ответом является последовательность из шагов 2, отсортированная по номерам строк