Python二进制数组场景下最优150项任务组合优化问题咨询

问题定位 #

这是经典的最大覆盖问题，属于NP难问题，目标是在指定可选元素数量限制下，最大化被覆盖的集合数量，正好匹配选150个任务、最大化覆盖成功时间列的需求。

方案1：贪心近似算法（推荐优先使用） #

最大覆盖问题的贪心解法有理论最优近似比（可达最优解的63%以上，即1-1/e），对于1000行×2000列的规模运行速度极快，远快于蒙特卡洛和精确求解器。
核心逻辑：每次选能覆盖最多「当前还没被覆盖的时间列」的任务，选满150个为止。
NumPy实现代码：

import numpy as np

def max_coverage_greedy(arr, select_k=150):
    n_rows, n_cols = arr.shape
    # 标记已覆盖的列
    covered = np.zeros(n_cols, dtype=bool)
    selected = []
    for _ in range(select_k):
        # 计算未选中任务能覆盖的未覆盖列数
        unselected_mask = ~np.isin(np.arange(n_rows), selected)
        uncovered_counts = arr[unselected_mask][:, ~covered].sum(axis=1)
        # 找到收益最高的任务索引
        best_task_idx = np.argmax(uncovered_counts)
        best_task = np.where(unselected_mask)[0][best_task_idx]
        selected.append(best_task)
        # 更新覆盖标记
        covered = covered | (arr[best_task] == 1)
        # 所有列都覆盖可提前终止
        if covered.all():
            break
    return selected, covered.sum()

该方法在当前数据规模上跑完全程最多几秒，效果远优于随机蒙特卡洛方案。

方案2：PuLP整数规划精确求解 #

如果需要严格的全局最优解，可以用PuLP搭建0-1整数规划模型，具体定义如下：

变量定义

• 设x[i]为0-1变量，x[i]=1代表选第i个任务，x[i]=0代表不选
• 设y[j]为0-1变量，y[j]=1代表第j个时间列被覆盖，y[j]=0代表未被覆盖

约束条件

1. 选择的任务总数等于150：$\sum_{i=0}^{999} x[i] = 150$
2. 时间列j被覆盖的前提是至少有一个选中的任务在j列取值为1：$\sum_{i \in S_j} x[i] \geq y[j]$，其中$S_j$是所有第j列为1的任务索引集合

目标函数

最大化被覆盖的时间列总数：$\max \sum_{j=0}^{1999} y[j]$

对应的PuLP实现代码：

import pulp
import numpy as np

def max_coverage_pulp(arr, select_k=150):
    n_rows, n_cols = arr.shape
    # 初始化问题
    prob = pulp.LpProblem("MaxCoverage", pulp.LpMaximize)
    # 定义变量
    x = pulp.LpVariable.dicts("x", range(n_rows), lowBound=0, upBound=1, cat="Binary")
    y = pulp.LpVariable.dicts("y", range(n_cols), lowBound=0, upBound=1, cat="Binary")
    # 添加目标函数
    prob += pulp.lpSum([y[j] for j in range(n_cols)])
    # 约束1：选150个任务
    prob += pulp.lpSum([x[i] for i in range(n_rows)]) == select_k
    # 约束2：覆盖逻辑约束
    for j in range(n_cols):
        valid_tasks = np.where(arr[:, j] == 1)[0].tolist()
        if len(valid_tasks) == 0:
            # 该列所有任务都失败，直接固定y[j]为0
            prob += y[j] == 0
        else:
            prob += pulp.lpSum([x[i] for i in valid_tasks]) >= y[j]
    # 求解，可设置timeLimit限制最大运行时间，单位为秒
    prob.solve(pulp.PULP_CBC_CMD(msg=False, timeLimit=300))
    # 提取结果
    selected = [i for i in range(n_rows) if pulp.value(x[i]) > 0.5]
    coverage = sum(pulp.value(y[j]) for j in range(n_cols))
    return selected, coverage

精确求解的时间随数据分布变化较大，如果跑太久可调整时间限制，CBC求解器会返回截止到时间限制时找到的最优可行解。

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