Максимизируйте сумму «не -перекрывающихся» чисел из матрицы

Просто ища немного направления, я понимаю, что приведенный пример можно решить, используя итерацию грубой силы, но я ищу более элегантный (т.е. математический? )решение, которое потенциально могло бы решить значительно большие примеры (, скажем, 20x20 или 30x30 ). Вполне возможно, что это невозможно сделать, и мне очень мало удалось найти подход, не основанный на грубой силе...

У меня есть матрица (, назовем ее A ), которая это nxn. Я хочу выбрать подмножество (, назовем его B )точек из матрицы A. Подмножество будет состоять из n элементов, где один и только один элемент берется из каждой строки и из каждого столбца A. Выход должен предоставить решение (B )такое, что сумма элементов, составляющих B, является максимально возможным значением, учитывая эти ограничения (, например. 25 в приведенном ниже примере ). Если найдено несколько экземпляров B (, т.е. различных решений, которые дают одинаковую максимальную сумму )следует выбрать решение для B, которое имеет наибольший минимальный элемент.

B также может быть матрицей выбора, которая имеет размер nxn, но в которой только n искомых элементов отличны от -нуля.

Например :если A =

|5 4 3 2 1|
|4 3 2 1 5|
|3 2 1 5 4|
|2 1 5 4 3|
|1 5 4 3 2|

=> B будет

|5 5 5 5 5|

Однако, если A =

|5 4 3|
|4 3 2|
|3 2 1|

B =

|3 3 3|

, поскольку минимальный элемент B равен 3, что больше, чем для

|5 3 1|

или

|4 4 1|

, которые также оба сумма равна 9