如何选择n列以最小化每行最小值之和？优化算法时间复杂度

问题明确 #

我们需要从给定的店铺中选择最多n家，购买每种产品各一件（产品不可拆分，每家店库存充足），目标是让总花费最少。这个问题等价于：从价格矩阵中选择n列，计算每行（对应单个产品）在选中列中的最小值，最终让这些最小值的总和最小。

当前暴力枚举所有店铺组合的方式，时间复杂度为O(C(m,n)*k)（m为店铺总数，k为产品总数），当店铺数量m较大时，组合数C(m,n)会指数级增长，效率极低。

局限性说明 #

• 贪心算法无效：按店铺总价排序选择的思路不可行，比如某家店大部分产品价格极高，但少数产品价格远低于其他店，单独看总价很高，但加入选中集合后能大幅拉低总花费。
• 动态规划不适用：该问题不存在最优子结构——选n-1家店的最优解，加入任意一家店后不一定能得到选n家店的最优解，新店铺可能替换掉之前多个产品的最低价。

优化方案 #

1. 分支定界（Branch and Bound）算法 #

通过剪枝减少不必要的组合遍历，核心是提前判断分支是否有可能得到更优解，避免无效计算：

• 预处理：计算每个产品的全局最低价，作为理论最优总花费的下界。
• 分支遍历：按店铺顺序遍历"选/不选"的状态，维护当前已选店铺数量、当前总花费，以及剩余店铺能带来的最大潜在节省（即剩余店铺中，每个产品的价格与当前已选集合中该产品最低价的差值，取正的部分之和）。
• 剪枝逻辑：如果当前总花费加上剩余店铺的最大潜在节省，仍不小于当前已知的最优总花费，直接终止该分支的遍历。

这种方法在实际场景中能大幅减少计算量，尤其是当最优解能被快速找到时，后续大量分支会被直接剪枝。

2. 剪枝优化的枚举 #

如果店铺数量m不算极大，可以在暴力枚举基础上做以下优化：

• 提前终止：先计算所有店铺都选中时的总花费（即每行全局最低价之和），如果枚举中遇到某个组合的总花费等于这个值，直接终止，这就是最优解。
• 按潜力排序：先计算每个店铺的"贡献潜力"（比如该店能为多少产品提供次低价，或能带来的潜在节省总和），按潜力从高到低排序店铺，优先枚举更有潜力的组合，这样能更快找到最优解，更早触发剪枝。

3. 位掩码优化（适用于m≤20的场景） #

当店铺总数m不超过20时，可用位掩码表示店铺选择状态（每一位对应一家店是否被选中），遍历所有恰好有n位为1的掩码，计算对应总花费。位运算的效率比itertools.combinations更高，适合小规模场景。

示例代码（匹配题目价格表）：

import pandas as pd

# 题目中的价格表
df = pd.DataFrame({
    'Shop A': [10.00, 8.50, 15.00],
    'Shop B': [12.00, 9.99, 14.50],
    'Shop C': [9.99, 7.99, 16.99]
})
n = 2  # 最多光顾2家店
shop_count = len(df.columns)
best_total = float('inf')
best_combination = []

# 遍历所有恰好选中n家店的位掩码
for mask in range(1 << shop_count):
    if bin(mask).count('1') != n:
        continue
    # 获取当前掩码对应的店铺
    selected_shops = [df.columns[i] for i in range(shop_count) if (mask >> i) & 1]
    # 计算当前组合的总花费
    current_total = df[selected_shops].min(axis=1).sum()
    # 更新最优解
    if current_total < best_total:
        best_total = current_total
        best_combination = selected_shops

print(f"最优店铺组合：{best_combination}")
print(f"最少总花费：${best_total:.2f}")

4. 启发式算法（适用于大规模场景） #

当m和k都很大时，精确算法复杂度太高，可采用启发式算法快速得到近似最优解：

• 模拟退火：随机生成店铺组合，通过随机替换店铺迭代优化，接受更优解，偶尔接受较差解以跳出局部最优。
• 遗传算法：将店铺组合编码为染色体，通过选择、交叉、变异操作迭代进化，逐步逼近最优解。

这类算法能在短时间内得到接近最优的结果，适合对精度要求不是极端严格的大规模场景。

复杂度对比 #

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