Supongamos que tenemos una tabla de números como esta (podemos suponer que es una tabla cuadrada):

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

Su trabajo consiste en calcular la suma máxima de n números donde n es el número de filas o columnas de la tabla. La trampa es cada número debe provenir de una fila y columna únicas.

Por ejemplo, seleccionar los números en (0,0), (1,1), (2,2), (3,3) y (4,4) es aceptable, pero (0,0), (0 , 1), (2,2), (3,3) y (4,4) no se deben a que los dos primeros números se extrajeron de la misma fila.

Mi solución (risible) para este problema consiste en recorrer todas las permutaciones posibles de las filas y columnas. Esto funciona para cuadrículas pequeñas pero, por supuesto, es increíblemente lento a medida que n crece. Tiene O (n!) Complejidad de tiempo, si no me equivoco (muestra el código de Python a continuación).

Realmente creo que esto se puede resolver en mejor momento, pero no se me ocurre nada lo suficientemente inteligente.

Así que mi pregunta es, ¿qué algoritmo debería usarse para resolver esto?

Si ayuda, este problema parece Similar a problema de mochila.

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