345. 矩阵和(Matrix Sum)
我们把一个矩阵的“矩阵和”定义为：在矩阵中选取若干元素，使得任意两个被选元素不在同一行、也不在同一列，并且这些被选元素的和尽可能大时得到的最大和。
例如，下方矩阵的矩阵和为 \(3315\)（即 \(863+383+343+959+767\)）：
$$ \begin{bmatrix} 7 & 53 & 183 & 439 & 863\\ 497 & 383 & 563 & 79 & 973\\ 287 & 63 & 343 & 169 & 583\\ 627 & 343 & 773 & 959 & 943\\ 767 & 473 & 103 & 699 & 303 \end{bmatrix} $$求下列 \(15\times 15\) 矩阵的矩阵和：
$$ \begin{bmatrix} 7&53&183&439&863&497&383&563&79&973&287&63&343&169&583\\ 627&343&773&959&943&767&473&103&699&303&957&703&583&639&913\\ 447&283&463&29&23&487&463&993&119&883&327&493&423&159&743\\ 217&623&3&399&853&407&103&983&89&463&290&516&212&462&350\\ 960&376&682&962&300&780&486&502&912&800&250&346&172&812&350\\ 870&456&192&162&593&473&915&45&989&873&823&965&425&329&803\\ 973&965&905&919&133&673&665&235&509&613&673&815&165&992&326\\ 322&148&972&962&286&255&941&541&265&323&925&281&601&95&973\\ 445&721&11&525&473&65&511&164&138&672&18&428&154&448&848\\ 414&456&310&312&798&104&566&520&302&248&694&976&430&392&198\\ 184&829&373&181&631&101&969&613&840&740&778&458&284&760&390\\ 821&461&843&513&17&901&711&993&293&157&274&94&192&156&574\\ 34&124&4&878&450&476&712&914&838&669&875&299&823&329&699\\ 815&559&813&459&522&788&168&586&966&232&308&833&251&631&107\\ 813&883&451&509&615&77&281&613&459&205&380&274&302&35&805 \end{bmatrix} $$
分析：这是一个标准“指派问题”。每一行必须选一个元素，且列不能重复，本质是最大化
$$
\sum_{i=0}^{n-1} a_{i,\pi(i)}
$$
其中 \(\pi\) 是列的一个排列。对于 \(n=15\)，状态压缩动态规划可以在极短时间内得到最优解。
一、数学背景
把“选元素且不同行不同列”看成二分图匹配： - 左侧顶点是行； - 右侧顶点是列； - 边权是矩阵值。
题目等价于求最大权完美匹配。
虽然可以用匈牙利算法，但本题规模固定且较小，使用位掩码 DP 更直接。
二、算法设计
设 mask 是一个二进制集合，表示已经使用过的列。定义
$$
dp[\text{mask}] = \text{前 }k=\mathrm{popcount}(\text{mask})\text{ 行完成分配时的最大和}
$$
转移时，为第 \(k\) 行选择一个未被使用的列 \(c\)：
$$
dp[\text{mask}\cup\{c\}] = \max\left(dp[\text{mask}\cup\{c\}],\ dp[\text{mask}] + a_{k,c}\right)
$$
初值：dp[0]=0。
终值：dp[(1<<n)-1]。
这个定义保证：
- 任一合法选法都对应一条从 0 到全满掩码的路径；
- 转移只会选未使用列，因此天然满足列互异；
- 对每个状态取最大值，最终得到全局最优。
三、复杂度分析
- 状态数：\(2^n\)。
- 每个状态最多尝试 \(n\) 个列转移。
- 时间复杂度：\(O(n^2 2^n)\)（按行推进 + 列枚举）。
- 空间复杂度：\(O(2^n)\)。
当 \(n=15\) 时，计算量非常小，实测远低于 60 秒要求。
四、代码实现与说明
"""Project Euler 345 - Matrix Sum."""
from __future__ import annotations
from time import perf_counter
SAMPLE_MATRIX: tuple[tuple[int, ...], ...] = (
(7, 53, 183, 439, 863),
(497, 383, 563, 79, 973),
(287, 63, 343, 169, 583),
(627, 343, 773, 959, 943),
(767, 473, 103, 699, 303),
)
SAMPLE_EXPECTED = 3315
TARGET_MATRIX: tuple[tuple[int, ...], ...] = (
(7, 53, 183, 439, 863, 497, 383, 563, 79, 973, 287, 63, 343, 169, 583),
(627, 343, 773, 959, 943, 767, 473, 103, 699, 303, 957, 703, 583, 639, 913),
(447, 283, 463, 29, 23, 487, 463, 993, 119, 883, 327, 493, 423, 159, 743),
(217, 623, 3, 399, 853, 407, 103, 983, 89, 463, 290, 516, 212, 462, 350),
(960, 376, 682, 962, 300, 780, 486, 502, 912, 800, 250, 346, 172, 812, 350),
(870, 456, 192, 162, 593, 473, 915, 45, 989, 873, 823, 965, 425, 329, 803),
(973, 965, 905, 919, 133, 673, 665, 235, 509, 613, 673, 815, 165, 992, 326),
(322, 148, 972, 962, 286, 255, 941, 541, 265, 323, 925, 281, 601, 95, 973),
(445, 721, 11, 525, 473, 65, 511, 164, 138, 672, 18, 428, 154, 448, 848),
(414, 456, 310, 312, 798, 104, 566, 520, 302, 248, 694, 976, 430, 392, 198),
(184, 829, 373, 181, 631, 101, 969, 613, 840, 740, 778, 458, 284, 760, 390),
(821, 461, 843, 513, 17, 901, 711, 993, 293, 157, 274, 94, 192, 156, 574),
(34, 124, 4, 878, 450, 476, 712, 914, 838, 669, 875, 299, 823, 329, 699),
(815, 559, 813, 459, 522, 788, 168, 586, 966, 232, 308, 833, 251, 631, 107),
(813, 883, 451, 509, 615, 77, 281, 613, 459, 205, 380, 274, 302, 35, 805),
)
def validate_square_matrix(matrix: tuple[tuple[int, ...], ...]) -> None:
"""Ensure the input matrix is non-empty and square."""
if not matrix:
raise ValueError("Matrix must not be empty.")
size = len(matrix)
for row in matrix:
if len(row) != size:
raise ValueError("Matrix must be square.")
def max_matrix_sum(matrix: tuple[tuple[int, ...], ...]) -> int:
"""Compute the maximum assignment sum using bitmask dynamic programming."""
validate_square_matrix(matrix)
n = len(matrix)
full_mask = (1 << n) - 1
negative_inf = -10**18
dp = [negative_inf] * (1 << n)
dp[0] = 0
for mask in range(1 << n):
row = mask.bit_count()
if row >= n or dp[mask] == negative_inf:
continue
current = dp[mask]
for col in range(n):
if mask & (1 << col):
continue
next_mask = mask | (1 << col)
candidate = current + matrix[row][col]
if candidate > dp[next_mask]:
dp[next_mask] = candidate
return dp[full_mask]
def solve_once() -> tuple[int, float]:
"""Run one full solve on the target matrix and return answer with elapsed time."""
start = perf_counter()
answer = max_matrix_sum(TARGET_MATRIX)
elapsed = perf_counter() - start
return answer, elapsed
def benchmark(runs: int = 3) -> tuple[int, list[float]]:
"""Run the solver multiple times for stable timing measurements."""
times: list[float] = []
answer = -1
for _ in range(runs):
answer, elapsed = solve_once()
times.append(elapsed)
return answer, times
def main() -> None:
"""Validate the sample, solve the target case, and print benchmark metrics."""
sample_answer = max_matrix_sum(SAMPLE_MATRIX)
print(f"sample_matrix_sum = {sample_answer}")
assert sample_answer == SAMPLE_EXPECTED, (
f"Sample check failed: got {sample_answer}, expected {SAMPLE_EXPECTED}"
)
answer, times = benchmark(runs=3)
print(f"matrix_sum_15x15 = {answer}")
print(f"timings_seconds = {[round(t, 6) for t in times]}")
print(f"timing_avg_seconds = {sum(times) / len(times):.6f}")
print(f"timing_max_seconds = {max(times):.6f}")
if __name__ == "__main__":
main()
代码说明（按执行顺序）：
常量区
SAMPLE_MATRIX和SAMPLE_EXPECTED用于题目给出的样例校验。TARGET_MATRIX是题目要求计算的 \(15\times 15\) 矩阵输入。- 代码中没有把最终答案写成常量参与求解逻辑，结果完全由 DP 计算得到。
validate_square_matrix
- 先检查矩阵非空，避免空输入导致无意义状态。
- 再检查每行长度是否等于行数，确保是方阵，满足指派问题前提。
max_matrix_sum
n是矩阵大小，full_mask表示所有列都已使用。dp[mask]表示前bit_count(mask)行分配完成时的最大和。- 初始化
dp[0]=0，其余为极小值表示“不可达”。 - 枚举状态时，
row = mask.bit_count()自动定位当前待分配行。 - 枚举所有未使用列，形成
next_mask，并尝试更新最大值。 - 返回
dp[full_mask]即最终最优值。
solve_once
- 包装一次完整求解，并返回“结果 + 耗时”，便于后续性能统计。
benchmark
- 默认运行 3 次，记录每次耗时。
- 返回最后一次结果与耗时列表，用于计算平均值和最大值。
main
- 先计算样例并断言等于题面给出的 3315。
- 再对目标矩阵运行 3 次性能测试并打印统计。
- 主流程只输出程序计算结果，不在文档中写入最终答案数值。