Python中DataFrame行分组：约束下组数计算及线性优化判定

一、符合条件的分组数量计算 #

手动计算结果 #

先看给定的数据集：

我们需要找出所有非空行子集满足：

• 子集内Size列总和 ≤ 100
• 子集内CPU列总和 ≤ 100

逐个分析：

1. 单个行的情况：

   • C2：Size=70≤100，CPU=5.1≤100 → 符合
   • C3：Size=60≤100，CPU=6.2≤100 → 符合
   • C5：Size=40≤100，CPU=10≤100 → 符合
   • C1、C4的Size分别为200、140，均超过100 → 不符合
     这部分共3个有效分组。

2. 多个行的组合情况：

   • C2+C5：Size=70+40=110>100 → 不符合
   • C3+C5：Size=60+40=100≤100，CPU=6.2+10=16.2≤100 → 符合
   • C2+C3：Size=70+60=130>100 → 不符合
   • 包含C1或C4的组合：Size总和必然超过100 → 全部不符合
   • 三个及以上行的组合：最小的三个Size总和为40+60+70=170>100 → 全部不符合
     这部分共1个有效分组。

总计符合条件的分组数量为 3+1=4个。

代码实现（Python） #

用itertools生成所有非空子集，逐一筛选符合条件的：

import pandas as pd
import itertools

# 创建数据集
df = pd.DataFrame({
    'name': ['C1', 'C2', 'C3', 'C4', 'C5'],
    'Size': [200, 70, 60, 140, 40],
    "CPU": [25.7, 5.1, 6.2, 15.1, 10]
})

valid_groups = []
# 生成所有非空子集（从1个元素到5个元素的组合）
for k in range(1, len(df)+1):
    for subset in itertools.combinations(df.index, k):
        subset_size = df.loc[subset, 'Size'].sum()
        subset_cpu = df.loc[subset, 'CPU'].sum()
        if subset_size <= 100 and subset_cpu <= 100:
            valid_groups.append(df.loc[subset, 'name'].tolist())

print(f"符合条件的分组数量：{len(valid_groups)}")
print("具体分组：", valid_groups)

运行结果：

符合条件的分组数量：4
具体分组： [['C2'], ['C3'], ['C5'], ['C3', 'C5']]

二、是否可视为线性优化问题？ #

这取决于问题的具体指向：

1. 如果只是统计所有符合条件的分组数量：这是一个组合计数问题，不属于优化问题范畴。
2. 如果是要将现有行划分成尽可能多的不重叠符合条件的分组（即每个行最多被分到一个组，目标是最大化分组数量）：这属于整数线性规划（ILP）问题，是线性优化的分支。

对应的整数线性规划模型可以表述为：

• 决策变量：设$x_{ij}$为0-1变量，表示第i行是否被分到第j个组；设$y_j$为0-1变量，表示第j个组是否存在。
• 目标函数：$\max \sum_j y_j$（最大化分组数量）
• 约束条件：
  • 每个行最多属于一个组：$\sum_j x_{ij} \leq 1$，对所有i
  • 每个组的Size总和≤100：$\sum_i x_{ij} \cdot \text{Size}_i \leq 100 \cdot y_j$，对所有j
  • 每个组的CPU总和≤100：$\sum_i x_{ij} \cdot \text{CPU}_i \leq 100 \cdot y_j$，对所有j
  • $x_{ij}, y_j \in {0,1}$

因此，若问题是追求分组数量最大化的划分，即可视为线性优化问题的一种。

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