如何用Pandas快速找出覆盖最多客户的12种产品组合？

这个问题本质是最大覆盖问题（Maximum Coverage Problem），属于NP-hard问题，没法通过暴力枚举（8600多万种组合）快速得到精确解，但可以通过以下高效方法在可接受时间内得到近似最优解或精确解：

1. 贪心近似算法（最快最实用，有理论保证） #

核心逻辑：每次选择能为当前组合新增最多未覆盖客户的产品，重复12次。该算法能保证得到至少(1-1/e)≈63%的最优解，计算速度极快。

实现步骤（基于Pandas） #

先将原始数据转换为客户-产品的二进制矩阵（1表示客户购买过该产品，0表示未购买）：

# 假设原始DataFrame为df，包含customer_id和product_id列
customer_product_matrix = pd.crosstab(df['customer_id'], df['product_id'])
# 转换为二进制标记
customer_product_matrix = (customer_product_matrix > 0).astype(int)

然后执行贪心选择：

selected_products = []
covered_customers = set()

for _ in range(12):
    max_new_customers = -1
    best_product = None
    
    # 遍历所有未选中的产品，计算新增覆盖客户数
    for product in customer_product_matrix.columns:
        if product in selected_products:
            continue
        # 获取该产品覆盖的所有客户
        product_customers = set(customer_product_matrix[customer_product_matrix[product] == 1].index)
        # 计算新增未覆盖的客户数
        new_count = len(product_customers - covered_customers)
        
        if new_count > max_new_customers:
            max_new_customers = new_count
            best_product = product
    
    if best_product is None:
        break  # 无新增客户，提前终止
    selected_products.append(best_product)
    covered_customers.update(customer_product_matrix[customer_product_matrix[best_product] == 1].index)

print(f"选中产品组合：{selected_products}")
print(f"覆盖客户总数：{len(covered_customers)}")

优点：实现简单，计算速度极快（仅30*12次循环）；缺点：是近似解，不一定是全局最优，但绝大多数场景下足够满足需求。

2. 贪心+局部搜索（更接近最优解） #

在贪心得到的初始组合基础上，通过迭代替换单个产品来优化覆盖数，直到无法提升为止。

实现步骤 #

先基于贪心得到初始组合，再执行局部搜索：

def get_coverage(products):
    # 计算给定产品组合的覆盖客户数
    covered = customer_product_matrix[products].sum(axis=1) >= 1
    return len(covered[covered].index)

# 基于贪心结果初始化
current_products = selected_products.copy()
current_coverage = get_coverage(current_products)
improved = True

while improved:
    improved = False
    # 遍历每个已选中的产品，尝试替换为未选中产品
    for idx in range(len(current_products)):
        for candidate in customer_product_matrix.columns:
            if candidate in current_products:
                continue
            # 生成新组合
            new_products = current_products[:idx] + [candidate] + current_products[idx+1:]
            new_coverage = get_coverage(new_products)
            
            if new_coverage > current_coverage:
                current_products = new_products
                current_coverage = new_coverage
                improved = True
                break  # 找到提升就跳出，重新开始循环
        if improved:
            break

print(f"优化后产品组合：{current_products}")
print(f"优化后覆盖客户数：{current_coverage}")

优点：比单纯贪心更接近最优解；缺点：计算量略大于贪心，但远小于暴力枚举，适合对精度要求较高的场景。

3. 整数规划（精确解，适合小规模数据） #

如果客户规模不大（比如几万以内），可以用整数规划工具求解精确的最优解。

实现步骤（基于pulp库） #

import pulp

# 初始化规划问题
prob = pulp.LpProblem("MaxCustomerCoverage", pulp.LpMaximize)

# 定义变量：产品选中状态（1=选中，0=未选中）
products = customer_product_matrix.columns.tolist()
x = pulp.LpVariable.dicts("Product", products, cat='Binary')

# 定义变量：客户被覆盖状态（1=被覆盖，0=未被覆盖）
customers = customer_product_matrix.index.tolist()
y = pulp.LpVariable.dicts("Customer", customers, cat='Binary')

# 目标函数：最大化覆盖客户数
prob += pulp.lpSum(y[c] for c in customers)

# 约束1：必须选中12个产品
prob += pulp.lpSum(x[p] for p in products) == 12

# 约束2：客户被覆盖的前提是至少购买了一个选中的产品
for c in customers:
    bought_products = customer_product_matrix.columns[customer_product_matrix.loc[c] == 1].tolist()
    prob += pulp.lpSum(x[p] for p in bought_products) >= y[c]

# 求解
prob.solve(pulp.PULP_CBC_CMD(msg=False))  # msg=False关闭日志输出

# 提取结果
selected_exact = [p for p in products if pulp.value(x[p]) == 1]
coverage_exact = int(pulp.value(prob.objective))

print(f"精确解产品组合：{selected_exact}")
print(f"精确解覆盖客户数：{coverage_exact}")

优点：能得到全局最优解；缺点：当客户数超过10万时，求解时间会急剧增加，甚至无法完成。

方法选择建议 #

• 追求速度、对精度要求不极端：选贪心算法
• 想要更优解、愿意接受少量额外计算：选贪心+局部搜索
• 必须要精确解、且数据规模小：选整数规划

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