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

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