最大化表的总和,其中每个数字必须来自唯一的行和列

Question

假设我们有一个这样的数字表(我们可以假设它是一个方形表):

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

Answer 1

这是最大成本的二分匹配问题.解决它的经典方法是使用匈牙利算法.

基本上你有一个二分图:左边是行,右边是列.从行i到列的每个边j都有成本matrix[i, j].找到最大化成本的匹配.