algorithm - 最大化不同指数的总和

Question

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

Answer 1

这是 maximum matching in a weighted bipartite graph ，也称为 assignment problem .列和行是图形部分(分别是代理和任务)，单元格是边(分别是任务分配)。

Hungarian algorithm 有效地解决了这个问题这是多项式。