最大化矩阵行/列交集之和

Question

我正在寻找一种比暴力破解更好的算法。

给定一个 M x N 整数矩阵，确定行/列的集合，使得其交点处的所有元素的总和最大化。

以下是示例案例和解决方案。

Answer 1

这个问题是NP难问题。

我们可以通过减少最大派系问题来看到这一点。绘制尺寸为

G

的图表

n

。通过将每个顶点转换为列和行，将其转换为

n x n

对称矩阵，每条边为 1，对角线下方为 1，其他位置为

-n

。现在解决你的问题就是找到最大派系大小的平方。

寻找大小为

k

的派系是否存在是卡普的21个NP完全问题之一。找到最大团的大小是 NP 困难的。所以你的问题是 NP 难的。