求固定k列选择算法：最大化矩阵中1多于0的行数

问题描述 #

给定一个由0和1组成的矩阵，其中行数 ( m < 10000 )，列数 ( n < 1000 )。需要选择 ( k )（( k \leq n )）列，使得矩阵中1的数量多于0的行数达到最大值，求可行的解决算法（包括近似算法）。

示例矩阵 #

1 2 3 4 5 (列号)
=========
0 1 0 1 0
0 1 1 1 0
1 0 0 1 1
1 0 1 1 1
1 1 0 0 0

不同k值的最优结果 #

• ( k=1 )：最优为第4列，可得到4行满足1的数量多于0；
• ( k=2 )：最优为第4列搭配第1、2、3、5列中的任意一列，可得到2行满足条件；
• ( k=3 )：最优为第1、2、4列，可得到全部5行满足条件；
• ( k=4 )：存在多个最优组合（如(2,3,4,5)、(1,2,3,4)、(1,3,4,5)），可得到2行满足条件；
• ( k=5 )：只能选全部5列，可得到3行满足条件。

算法方案 #

问题复杂度分析 #

该问题属于NP-hard问题，当列数 ( n ) 较大时（如 ( n=1000 )），不存在多项式时间的精确算法（除非P=NP），因此实际场景中通常采用近似算法或针对小规模场景的精确算法。

1. 精确算法（仅适用于小规模n） #

当列数 ( n \leq 20 ) 时，可以直接枚举所有大小为 ( k ) 的列组合，对每个组合计算满足条件的行数，最终选择最优组合。但该方法时间复杂度为 ( O(C(n,k) \times m \times k) )，当 ( n \geq 30 ) 时就会因计算量过大无法使用。

2. 近似算法 #

贪心算法

核心思路：每次选择能让当前满足条件的行数增加最多的列，重复 ( k ) 次。具体步骤如下：

• 初始化已选列集合为空，满足条件的行数为0；
• 对于每一步，遍历所有未被选中的列，计算将该列加入已选集合后，整体满足条件的行数；
• 选择使行数提升最大的列加入集合；
• 重复上述步骤直到选满 ( k ) 列。

该算法实现简单，时间复杂度为 ( O(k \times n \times m) )，在大多数场景下能得到较优的近似解，但无法保证得到全局最优。

随机采样算法

核心思路：随机生成若干个大小为 ( k ) 的列组合，计算每个组合对应的满足条件的行数，最终保留最优的组合。具体操作：

• 重复采样数百至数千次（次数根据计算资源调整）；
• 每次采样随机挑选 ( k ) 个不重复的列；
• 记录所有采样中表现最好的组合。

该算法实现成本极低，时间复杂度可通过调整采样次数灵活控制，对于大规模矩阵是一种高效的近似方案。

线性规划松弛近似

将问题转化为整数线性规划（ILP），再松弛为线性规划（LP）求解，最后通过取整得到近似解：

• 定义0-1变量 ( x_j )：( x_j=1 ) 表示选中第 ( j ) 列，否则为0；
• 定义0-1变量 ( y_i )：( y_i=1 ) 表示第 ( i ) 行满足1的数量多于0，否则为0；
• 目标函数：最大化 ( \sum_{i=1}^m y_i )；
• 约束条件：
  1. ( \sum_{j=1}^n x_j = k )
  2. 对每一行 ( i )：( \sum_{j=1}^n x_j \times row[i][j] > \frac{k}{2} )（当 ( y_i=1 ) 时）
• 松弛后允许 ( x_j ) 和 ( y_i ) 取连续值，求解LP后，将 ( x_j ) 按取值从大到小排序，选取前 ( k ) 个列作为近似解。

该方法理论基础扎实，近似比有保障，但实现相对复杂，需要依赖LP求解器。

内容的提问来源于stack exchange，提问作者Ordev Agens