最大化不同指数的总和

Question

假设我有一个矩阵 A，大小为 n x p，每个元素为 n > p，每个元素为 0 <= A <= 1。我想在 A 中找到 p 个元素，每列一个，这样总和就会最大化，并且每个元素都在不同的行中。因此，需要考虑 n permute p 种不同的组合。这个问题有名字吗？我发现了诸如背包问题之类的问题，但是设置不同。此外，对于 n=300, p=10 来说，它们是否是任何有效的算法来计算这个？有一些特殊情况需要检查，例如每列中的最大值是否恰好在不同的行上。否则，我会留给动态规划吗？谢谢！

Answer 1

这是maximum matching in a weighted bipartite graph, also known as the assignment problem。列和行是图形部分（分别是代理和任务），单元格是边（分别是任务分配）。

这可以通过多项式的 Hungarian algorithm 有效解决。