假设我们有一个这样的数字表（我们可以假设它是一个方形表）：

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