Как найти комбинацию чисел, которая в сумме (или ближе) соответствует заданной цели? ⇐ Python

[Anonymous]

Мой ввод — это список слов, соответствующих задачам:

Код: Выделить всё

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'},
]

Моя цель — найти случайную комбинацию задач, в которой:

• Количество ожидающих задач точно соответствует указанному
• Общий объем максимально приближен к заданному целевому объему.

Для этого я сделал код ниже но в моем реальном наборе данных он работает очень медленно (~ 10 тыс. задач), и я также не доверяю ему, потому что чувствую, что иногда он не дает правильной комбинации.

Код: Выделить всё

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

Ребята, у вас есть идеи, как исправить мой код?

Ограничения проблемы

• Код: Выделить всё

  tasks: list[dict]

  имеет размер 10**4

• Код: Выделить всё

  number_ids

  может иметь значение от 1 до 10,

• Код: Выделить всё

  target_volume

  варьируется от 50 до максимального значения 1000

• Код: Выделить всё

  task['VOLUME']

  всегда представляет собой целое число от 1 до 300.

Подробнее здесь: https://stackoverflow.com/questions/789 ... ven-target