从二维数组选L行以最小化列最小值之和的高效解法问询

给定一个形状为(N,M)的二维数组，需要从中选取L行组成子数组SUB_M；对SUB_M的每一列取最小值得到一维数组ANS_M，目标是最小化ANS_M的元素总和。

问题示例 #

原数组：

[[  8   7   7   7   7   7   7   5   6]
 [  5   7   6   5   6   6   7   7   5]
 [  7   8   8   8   5   5   5   6   7]
 [  7   8   7   7   7   6   7   8   5]
 [  0   0 100 100 100 100 100 100 100]
 [100 100 100   0   0 100 100 100 100]
 [100 100 100 100 100 100   0   0 100]]

选取行1、4、5、6后得到SUB_M：

[[  5   7   6   5   6   6   7   7   5]
 [  0   0 100 100 100 100 100 100 100]
 [100 100 100   0   0 100 100 100 100]
 [100 100 100 100 100 100   0   0 100]]

对应的ANS_M为：

[  0   0   6   0   0   6   0   0   5]

总和为17，是当前最优解。

问题难点 #

暴力枚举所有C(N,L)种组合的时间复杂度为O(C(N,L)*M)，当N和L较大时（比如N=50，L=25），C(50,25)约为2.25e13，完全不可行。此外，该问题不能通过简单的最小堆或基于行和的贪心解决——例如：

A = [ 5  5  5  5  5]
B = [ 0  0  0 99 99]
C = [99 99 99  0  0]

单独选A的行和为25，而选B+C的组合后，各列最小值之和为0，远优于选A的结果，说明行的单独性能无法代表组合后的整体性能。

高效解法思路 #

1. 分支定界法（精确解法，适用于N、L中等规模）

基于枚举的剪枝策略，通过计算当前分支的下界来提前终止不可能得到更优解的路径：

• 状态跟踪：记录已选的k行，以及当前各列的最小值curr_min[j]、当前总和curr_sum。
• 下界计算：对于每列j，计算剩余未选行中该列的最小值rem_min[j]，则该列的最终最小可能值为min(curr_min[j], rem_min[j])，所有列的这个值之和就是当前分支的下界。
• 剪枝条件：如果curr_sum + 下界 >= 当前已知最优解，则直接跳过该分支，不再枚举剩余行的选择。
• 优化：可以先对行进行预处理，按行能带来的列最小值潜力排序，优先枚举更可能得到优解的分支，加速剪枝。

2. 整数规划建模（精确解法，适用于中等规模问题）

将问题转化为整数规划模型，借助成熟的求解器求解：

• 变量定义：
  • 二进制变量x_i：x_i=1表示选中第i行，x_i=0表示不选。
  • 连续变量y_j：表示第j列的最小值。
• 目标函数：minimize Σ(y_j)，即最小化各列最小值之和。
• 约束条件：
  1. 选中行的数量约束：Σ(x_i) = L
  2. 列最小值约束：对于每个列j和行i，y_j <= arr[i][j] + M*(1 - x_i)，其中M是数组中的最大值（确保当x_i=1时，y_j不超过该行第j列的值；当x_i=0时，约束自动失效）。
  3. 非负约束：y_j >= 0

3. 启发式贪心算法（近似解法，适用于大规模数据）

当数据规模过大无法使用精确解法时，可以采用启发式贪心策略快速得到近似最优解：

• 策略1：迭代替换
  1. 先随机或按行和选取初始的L行，计算当前总和。
  2. 尝试用未选中的每行替换选中的某一行，计算替换后的总和，保留能使总和减小的替换。
  3. 重复步骤2，直到无法找到更优的替换为止。
• 策略2：覆盖优先
  1. 对于每列j，记录当前全局最小值global_min[j]，以及哪些行能达到这个最小值。
  2. 优先选择能覆盖多个未被覆盖的global_min[j]的行，逐步选中L行，最后调整优化。

4. 动态规划（适用于M较小的场景）

当列数M较小时，可以用状态压缩DP：

• 状态定义：dp[k][mask]表示选了k行，各列当前最小值为mask对应的数值时的最小总和（这里的mask可以用元组或编码表示各列的最小值状态，但仅适用于M很小的情况，比如M<=10）。
• 状态转移：对于每个状态dp[k][mask]，尝试加入第i行（未被选中过），计算新的列最小值状态new_mask（每列取mask[j]和arr[i][j]的较小值），更新dp[k+1][new_mask]为更小的总和。

总结 #

• 小规模问题（N<=30, L<=15）：分支定界法效率较高。
• 中等规模问题：整数规划求解器能给出精确解。
• 大规模问题：启发式贪心算法可以在可接受时间内得到近似最优解。

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