如何优化指定数量等待任务的组合匹配代码？解决大数据集效率问题

测试任务列表 #

tasks = [
    {'ID': 'ID_001', 'VOLUME': 50, 'STATUS': 'ENDED_OK'},
    {'ID': 'ID_002', 'VOLUME': 10, 'STATUS': 'WAITING'},
    {'ID': 'ID_003', 'VOLUME': 10, 'STATUS': 'WAITING'},
    {'ID': 'ID_004', 'VOLUME': 20, 'STATUS': 'WAITING'},
    {'ID': 'ID_005', 'VOLUME': 10, 'STATUS': 'ONGOING'},
    {'ID': 'ID_006', 'VOLUME': 10, 'STATUS': 'WAITING'},
    {'ID': 'ID_007', 'VOLUME': 25, 'STATUS': 'WAITING'},
]

需求目标 #

找到一组任务组合，满足：

• 恰好包含指定数量的WAITING状态任务
• 总VOLUME尽可能接近给定的目标容量

当前实现代码 #

import itertools

def find_combination(tasks, number_ids, target_volume=50):
    waiting_tasks = [task for task in tasks if task['STATUS'] == 'WAITING']

    sorted_tasks = sorted(waiting_tasks, key=lambda x: x['VOLUME'], reverse=True)

    closest_combination = []
    closest_volume_diff = float('inf')

    for combination in itertools.combinations(sorted_tasks, number_ids):
        total_volume = sum(task['VOLUME'] for task in combination)
        volume_diff = abs(total_volume - target_volume)

        if volume_diff < closest_volume_diff:
            closest_combination = combination
            closest_volume_diff = volume_diff

        if volume_diff == 0:
            break

    return [task['ID'] for task in closest_combination], sum(
        task['VOLUME'] for task in closest_combination
    )

测试运行结果 #

ids_selected, total_volume = find_combination(tasks, 3, target_volume=50)
print(f'Selected IDs: {ids_selected}, Total Volume: {total_volume}')
# 输出结果: Selected IDs: ['ID_007', 'ID_004', 'ID_002'], Total Volume: 55

问题与优化请求 #

上述代码在小规模测试数据上可以正常运行，但在包含约10000个任务的真实数据集里运行极慢，且存在无法给出正确组合的可能性。请提供优化这段代码的思路。

问题约束 #

• tasks: list[dict]规模为10**4
• number_ids取值范围为1至10
• target_volume取值范围为50至1000
• task['VOLUME']始终为1至300之间的整数

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