Pandas筛选列求和约束下最小化另一列总和的行子集方案咨询

这个需求本质是0-1最小费用背包问题的变种，约束为选中行的Target列总和≥指定阈值，优化目标为选中行的Cost列总和最小，以下是具体实现思路和可用工具：

实现思路 #

• 小数据量场景（行数≤20）：可以直接暴力枚举所有行组合，遍历所有可行解取Cost最小的即可，逻辑简单不易出错，示例代码如下：

import pandas as pd
import itertools

df = pd.DataFrame({'Names': ['a', 'b', 'c', 'd', 'e', 'f'],
               'Target': [35, 15, 12, 8, 7, 5],
               'Cost': [15, 40, 30, 30, 25, 10]})
threshold = 40
min_cost = float('inf')
best_comb = None

# 枚举所有可能的行组合长度
for n in range(1, len(df)+1):
    # 枚举所有长度为n的行组合
    for comb in itertools.combinations(df.index, n):
        total_target = df.loc[comb, 'Target'].sum()
        if total_target >= threshold:
            total_cost = df.loc[comb, 'Cost'].sum()
            if total_cost < min_cost:
                min_cost = total_cost
                best_comb = comb

# 输出结果
print("最优选中行：")
print(df.loc[best_comb])
print(f"Target总和：{df.loc[best_comb, 'Target'].sum()}")
print(f"最小Cost总和：{min_cost}")

运行上述代码即可得到示例中的最优解：选中行a和f，Cost总和25。

• 大数据量场景（行数>20）：用动态规划的背包解法优化，定义状态dp[i]为凑出Target总和为i时的最小Cost，状态长度可以设为min(所有行Target总和, 阈值 + 单条最大Target)，超过阈值的部分无需精确计算，统一按阈值处理即可节省空间，遍历所有行更新状态后，取dp[阈值]及以上的最小值即为最优解，回溯状态即可拿到选中的行。

可用开发库 #

如果不想自行实现逻辑，可以直接用运筹优化库求解，无需手动推导动态规划规则：

• PuLP：轻量的Python线性规划库，支持定义整数变量、约束和优化目标，使用门槛低，示例代码如下：

from pulp import LpProblem, LpMinimize, LpVariable, lpSum, value

# 定义0-1变量，1代表选中对应行，0代表不选
x = [LpVariable(f"x_{i}", cat="Binary") for i in df.index]
# 初始化问题，目标为最小化Cost总和
prob = LpProblem("min_cost_target", LpMinimize)
# 添加目标函数
prob += lpSum([x[i] * df.loc[i, "Cost"] for i in df.index])
# 添加约束：Target总和≥阈值
prob += lpSum([x[i] * df.loc[i, "Target"] for i in df.index]) >= threshold
# 求解
prob.solve()
# 提取选中的行
selected = [i for i in df.index if value(x[i]) == 1]
print(df.loc[selected])

• OR-Tools：谷歌出品的运筹优化工具包，求解效率更高，适合万级以上行的大规模场景。

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