[Python] How to find the combination of numbers that sum (or closer) to a given target?

My input is a list of dicts that correspond to tasks :

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


My goal is to find a random combination of tasks where:

• The number of waiting tasks is exactly as specified
• The total volume is as close as possible to a given target volume

For that I made the code below but it's extremely slow in my real dataset (~10k tasks) and I also don't trust it because I feel like sometimes it doesn't give the right combination.

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


Do you guys have an idea on how to fix my code ?


Constraints of the problem

• tasks: list[dict] is of size 10**4
• number_ids can be from 1 to 10,
• target_volume ranges from 50 to a max of 1000
• task['VOLUME'] is always an integer between 1 to 300.

Continue reading...