c++ - 来自不同行和列的矩阵每个元素的最大总和

Question

我有一个我自己无法处理的问题。问题是我需要找到矩阵元素的最大总和，使得每个元素都来自不同的列和行。例子：

{[1, 5 ,2],

[0,3, 2 ],

[ 9,0,1 ]}

这个矩阵的输出是 5+2+9=16。我知道有一些算法可以解决它，但我还没有达到这个水平，所以我想通过蛮力解决它，但我真的不知道如何解决。如果您能给我一些提示或伪代码，我将不胜感激。

_________________编辑_____________

如果有人有同样的问题并想在不使用 STL 的情况下实现下一个排列的算法，我给你留下这篇文章，它对我有很大帮助。https://www.programcreek.com/2014/06/leetcode-next-permutation-java/

Answer 1

用蛮力解决此任务的一种可能方法是：

1. 放result = MIN
2. 创建一个包含值的容器a = {0, ..., n-1}
3. 计算sum = matrix[0][a[0]] + ... + matrix[n-1][a[n-1]]
4. 设置result为max(result, sum)
5. 如果有 的另一个排列a，则排列a并转到 3。
6. 返回result

STL 将通过std::next_permutation、std::max、std::iota、std::accumulate、std::vector、std::array、std::numeric_limits让您的生活更轻松......