给定一个矩阵 A，我正在寻找 p 列的集合，使每行中匹配单元格总和的最小值最大化。
例如:如果 p=2 且 A=
1 2 4
3 0 3
5 6 2
选择 C1 和 C2 将得到 f=min(r1,r2,r3)=min(1+2; 3+0; 5+6)=3
选择C1和C3会得到f=min(1+4; 3+3; 5+2)=5，这是最好的选择。
是否有任何算法或启发式这样做..
谢谢
最佳答案
这个问题是 NP 困难的，通过对集合覆盖进行简单的简化(令 A 为表示元素集包含关系的 0-1 矩阵)。我会在简单的整数规划公式上尝试使用 MIP 求解器，其中如果采用第 j 列，则 c(j) 为 1，否则为 0。
maximize lambda
subject to
lambda <= c(1) A(i,1) + ... + c(n) A(i,n) for all i
c(1) + ... + c(n) = p
c(j) in {0, 1} for all j
关于algorithm - 找到使每行总和最小值最大化的列集，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/6890018/