Максимизировать сумму таблицы, где каждое число должно происходить из уникальной строки и столбца

Предположим, у нас есть такая таблица чисел (мы можем предположить, что это квадратная таблица):

20  2   1   3   4
5   1   14  8   9
15  12  17  17  11
16  1   1   15  18
20  13  15  5   11

Ваша задача - вычислить максимальную сумму n чисел, где n - количество строк или столбцов в таблице. Уловка состоит в том, что каждое число должно происходить из уникальной строки и столбца.

Например, выбор чисел в (0,0), (1,1), (2,2), (3,3) , и (4,4) приемлемо, но (0,0), (0,1), (2,2), (3,3) и (4,4) нет, потому что первые два числа были вытянуты из той же строки.

Мое (смехотворное) решение этой проблемы заключается в переборе всех возможных перестановок строк и столбцов. Это работает для небольших сеток, но, конечно, невероятно медленно, когда n становится большим. У него O (n!) Временная сложность, если я не ошибаюсь (пример кода Python ниже).

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

Итак, мой вопрос: какой алгоритм следует использовать для решения этой проблемы?

Если это помогает, эта проблема кажется похожей на проблема с рюкзаком .

import itertools
import re

grid = """20    2   1   3   4
5   1   14  8   9
15  12  17  17  11
16  1   1   15  18
20  13  15  5   11"""
grid = [[int(x) for x in re.split("\s+", line)] for line in grid.split("\n")]

possible_column_indexes = itertools.permutations(range(len(grid)))
max_sum = 0
max_positions = []
for column_indexes in possible_column_indexes:
    current_sum = 0
    current_positions = []
    for row, col in enumerate(column_indexes):
        current_sum += grid[row][col]
        current_positions.append("(%d, %d)" % (row, col))
    if current_sum > max_sum:
        max_sum = current_sum
        max_positions = current_positions

print "Max sum is", max_sum
for position in max_positions:
    print position