基于SciPy Minimize筛选n组最优双人组合（带薪资约束）

核心思路 #

问题本质是带约束的多组合优化：要满足人员不重复、每组薪资≤限额，同时最大化总技能总和。针对千级规模数据，必须摒弃全量遍历或多次单组优化的低效方式，改用排序+贪心+剪枝，或专用整数规划求解器的策略。

具体实现方案 #

1. 预排序与候选池快速构建 #

• 先将所有人员按技能/薪资比降序排序，优先保留性价比高的人员，快速缩小候选范围。
• 用双指针法预计算所有符合薪资限额的组合：排序后，对每个人员i，从末尾向前找最大的j使得两人薪资和≤限额，时间复杂度从O(n²)降到O(n log n)。
• 将所有有效组合按技能总和降序排序，后续遍历优先处理高价值组合。

2. 贪心+剪枝的迭代筛选 #

• 每次取出当前技能总和最高的有效组合，标记组合内两人为已使用。
• 从候选池中移除所有包含这两人的组合，避免重复选择。
• 剪枝优化：若剩余候选组合的最大技能总和×剩余需选组数，小于当前已选组合的总技能，直接停止遍历，跳过无效计算。

3. 整数规划建模（全局最优适配） #

如果需要精准的全局最优解，可将问题建模为0-1整数规划，用专门的求解器（如ortools.linear_solver）替代scipy通用优化器：

• 变量：设x_ij为0或1，表示是否选择人员i和j的组合（i<j避免重复计数）
• 目标函数：最大化sum(x_ij * (skill_i + skill_j))
• 约束条件：
  • 每组薪资合规：x_ij * (salary_i + salary_j) ≤ budget（所有i<j）
  • 人员不重复：sum(x_ij for all j≠i) ≤ 1（所有i）
  • 选满n组：sum(x_ij) = n
• 优势：ortools的整数规划求解器针对大规模问题有启发式优化，性能远优于scipy通用方法，可轻松处理千级人员数据。

4. 性能优化细节 #

• 用numpy数组存储人员数据，避免Python循环的性能损耗。
• 用哈希表记录已使用人员，快速过滤包含已用人员的组合。
• 若n较大（超过总人员数1/2），可反向筛选：先排除技能最低的无效组合，再选取最优子集。

示例代码片段（双指针预筛选组合） #

import numpy as np

# 人员数据格式：(技能值, 薪资)
people = np.array([(10, 5), (9, 4), (8, 3), (7, 2), (6, 1)], dtype=[('skill', int), ('salary', int)])
budget = 7

# 按技能/薪资比降序排序
people = np.sort(people, order=['skill', 'salary'])[::-1]

valid_pairs = []
n_total = len(people)
j = n_total - 1

for i in range(n_total):
    # 双指针找最大j，满足薪资和不超预算
    while j > i and people[i]['salary'] + people[j]['salary'] > budget:
        j -= 1
    # 收集i的所有有效搭档，按技能和降序
    for k in range(i+1, j+1):
        valid_pairs.append((people[i]['skill'] + people[k]['skill'], i, k))

# 按技能总和降序排序，优先处理高价值组合
valid_pairs.sort(reverse=True)

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