嘿，我懂你现在的烦恼——暴力枚举所有组合来求这个最大和确实太低效了，尤其是矩阵规模稍微大一点，运算量直接上天（比如n阶方阵就是O(n!)的复杂度，n=10都要算360多万次，n=15就完全扛不住了）。其实你的问题本质就是带权二分图的最大权匹配问题，也就是经典的「指派问题」的最大化版本，早就有成熟的高效解法了。

核心最优解法：最大化版匈牙利算法 #

标准匈牙利算法是用来解决最小权指派问题的，但我们只需要做一点小修改就能适配你的最大化需求：

1. 先找到矩阵中的最大值，用这个最大值减去矩阵里的每一个元素，把原问题转化为最小权指派问题
2. 用标准匈牙利算法求解转换后的最小权问题
3. 最后用「最大值×矩阵阶数」减去得到的最小和，就是原问题的最大和

举个直观例子 #

假设你的矩阵是：

[ [3, 1, 2],
  [4, 2, 5],
  [1, 6, 3] ]

矩阵最大值是6，转换后的最小权矩阵为：

[ [3,5,4],
  [2,4,1],
  [5,0,3] ]

用匈牙利算法算出最小和是3+1+0=4，原问题的最大和就是 6×3 - 4 = 14，对应选中的元素是第一行3、第二行5、第三行6，正好每行每列各一个，完全符合约束条件。

其他可选思路（针对小规模或特殊场景） #

• 状态压缩动态规划（仅适用于方阵）：如果是n×n的方阵，可以用二进制数表示列的选中状态，比如dp[mask]表示选中mask对应列时的最大和。转移方程为dp[mask | (1<<j)] = max(dp[mask | (1<<j)], dp[mask] + matrix[i][j])，其中i是当前处理的行，j是未被选中的列。不过这个方法复杂度是O(n²×2ⁿ)，n超过15就不太实用了。
• 回溯剪枝：如果矩阵规模很小（比如n≤10），可以在暴力遍历基础上加剪枝逻辑——比如当前已选元素的和加上剩余行的最大可能元素和，都小于当前已知的最大和，就直接放弃这条分支，能大幅减少计算量。

Python代码示例（最大化版匈牙利算法） #

def max_assignment(matrix):
    n = len(matrix)
    m = len(matrix[0])
    assert n == m, "该实现仅支持方阵，非方阵可调整为方阵后使用"
    
    # 将最大化问题转换为最小化问题
    max_val = max(max(row) for row in matrix)
    cost_matrix = [[max_val - val for val in row] for row in matrix]
    
    # 标准匈牙利算法求解最小权指派
    u = [0] * (n + 1)
    v = [0] * (n + 1)
    p = [0] * (n + 1)
    way = [0] * (n + 1)
    
    for i in range(1, n + 1):
        p[0] = i
        minv = [float('inf')] * (n + 1)
        used = [False] * (n + 1)
        j0 = 0
        while True:
            used[j0] = True
            i0 = p[j0]
            delta = float('inf')
            j1 = 0
            for j in range(1, n + 1):
                if not used[j]:
                    cur = cost_matrix[i0 - 1][j - 1] - u[i0] - v[j]
                    if cur < minv[j]:
                        minv[j] = cur
                        way[j] = j0
                    if minv[j] < delta:
                        delta = minv[j]
                        j1 = j
            for j in range(n + 1):
                if used[j]:
                    u[p[j]] += delta
                    v[j] -= delta
                else:
                    minv[j] -= delta
            j0 = j1
            if p[j0] == 0:
                break
        while True:
            j1 = way[j0]
            p[j0] = p[j1]
            j0 = j1
            if j0 == 0:
                break
    
    # 计算原问题的最大和，同时返回选中的元素
    max_sum = max_val * n + v[0]
    selected_elements = [0] * n
    for j in range(1, n + 1):
        selected_elements[p[j] - 1] = matrix[p[j] - 1][j - 1]
    
    return max_sum, selected_elements

# 测试示例
test_matrix = [
    [3, 1, 2],
    [4, 2, 5],
    [1, 6, 3]
]
result_sum, selected = max_assignment(test_matrix)
print(f"最大和: {result_sum}")
print(f"选中的元素（按行顺序）: {selected}")

这个算法的时间复杂度是O(n³)，比暴力枚举高效太多，哪怕是n=100的方阵也能轻松处理。

内容的提问来源于stack exchange，提问作者Barrelo