最大化表的总和，其中每个数字必须来自唯一的行和列 [英] Maximize sum of table where each number must come from unique row and column

问题描述

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

Suppose we have a table of numbers like this (we can assume it is a square table):

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是表中的行数或列数。要注意的是，每个数字都必须来自唯一的行和列。

Your job is to calculate the maximum sum of n numbers where n is the number of rows or columns in the table. The catch is each number must come from a unique row and column.

例如，选择（0,0），（ 1,1），（2,2），（3,3）和（4,4）是可接受的，但（0,0），（0,1），（2,2），（3,3） ，和（4,4）并不是因为前两个数字是从同一行中提取的。

For example, selecting the numbers at (0,0), (1,1), (2,2), (3,3), and (4,4) is acceptable, but (0,0), (0,1), (2,2), (3,3), and (4,4) is not because the first two numbers were pulled from the same row.

我对此问题的（可笑的）解决方案是遍历所有可能的情况行和列的排列。这适用于小网格，但是，当然，随着n变大，它的速度非常慢。如果我没记错的话，它的时间复杂度为O（n！）（下面的示例Python代码）。

My (laughable) solution to this problem is iterating through all the possible permutations of the rows and columns. This works for small grids but, of course, it is incredibly slow as n gets big. It has O(n!) time complexity, if I'm not mistaken (sample Python code below).

我真的认为这可以在更好的时间内解决，但是我没有提出足够聪明的东西。

I really think this can be solved in better time, but I'm not coming up with anything sufficiently clever.

所以我的问题是，应该使用哪种算法来解决这个问题？

So my question is, what algorithm should be used to solve this?

如果有帮助，则该问题似乎与
背包问题相似a>。

If it helps, this problem seems similar to the knapsack problem.

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

推荐答案

这是最大成本的两方匹配问题。解决此问题的经典方法是使用匈牙利算法。

This is the maximum cost bipartite matching problem. The classical way to solve it is by using the Hungarian algorithm.

基本上，您有一个二部图：左组是行，右组是列。从行 i 到列 j 的每个边的成本为 matrix [i，j] 。找到使费用最大化的匹配项。

Basically you have a bipartite graph: the left set is the rows and the right set is the columns. Each edge from row i to column j has cost matrix[i, j]. Find the matching that maximizes the costs.

这篇关于最大化表的总和，其中每个数字必须来自唯一的行和列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！