只是寻找一点方向，我意识到给出的例子可以使用强力迭代来解决，但我正在寻找一个更优雅(即数学？)的解决方案，它可能会解决更大的例子(比如20x20 或 30x30)。这完全有可能无法做到，而且我在提出一种不依赖蛮力的方法方面收效甚微......
我有一个 nxn 的矩阵(称之为 A)。我希望从矩阵 A 中选择一个点的子集(称为 B)。该子集将由 n 个元素组成，其中一个且只有一个元素取自 A 的每一行和每一列。输出应提供一个解决方案( B) 使得构成 B 的元素的总和是最大可能值，给定这些约束(例如下例中的 25)。如果发现 B 的多个实例(即给出相同最大和的不同解决方案)，则应选择具有最大最小元素的 B 的解决方案。
B 也可以是 nxn 的选择矩阵，但其中只有 n 个所需元素是非零的。
例如: 如果 A =
|5 4 3 2 1|
|4 3 2 1 5|
|3 2 1 5 4|
|2 1 5 4 3|
|1 5 4 3 2|
=> B 会是
|5 5 5 5 5|
但是，如果 A =
|5 4 3|
|4 3 2|
|3 2 1|
乙=
|3 3 3|
因为B的最小元素是3，大于
|5 3 1|
或
|4 4 1|
两者的和也是 9
最佳答案
您的问题几乎与 Assignment problem 相同，这可以例如由 Hungarian algorithm 解决在多项式时间内。
请注意，赋值问题通常是一个最小化问题，但是将矩阵乘以 -1 并添加一些常数应该可以使该方法适用。此外，对于多个最优解的情况，没有正式的限制条件。但是，该方法会为您提供具有最佳总和的解决方案。令 m 为最小加数。通过将小于或等于 m 的所有条目设置为零来修改矩阵，然后再次求解。要么你得到一个总和比上一个更好的解决方案。如果不是，则之前的解决方案已经是最优的。
关于algorithm - 最大化矩阵中 "non-overlapping"数字的总和，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/26555623/