I have a question that is algorithms and CS related but felt more appropriate to ask on Math Exchange.
I have a list of candidates, each with a given duration. for example {candidate1: 15s, candidate2: 15s, candidate3: 30s, candidate 4: 30s, candidate5: 10s} and the number of candidates can become very high.
I am given bounds of a minimum duration and a maximum duration, where i need to choose a combination of those candidates that satisfies those bounds. For example mind = 41 seconds, and maxd = 45 seconds.
The goal is to always choose a combination of candidates that satisfies those limits, but I cannot be sure which candidate will be chosen first and it is not possible to backtrack once a candidate is chosen. This creates the problem of choosing faulty durations that make it impossible to satisfy the given boundaries. For example, if the list in the example previously was considered, choosing candidate5 first would make it impossible to create a duration that satisfies the given limits. This is becuase 10s can not be combined with the other candidates to create a total between 41 and 45. Although a valid combination for those limits does exist with the given list of candidates, for instance, 30s and 15s.
I can not use a knapsack approach because the candidates might have rules between them that make them incompatible with each other, meaning if one candidate is selected the other might not be selectable and the possible items for the knapsack change.
So I would like to filter out candidates that I know for sure, will not satisfy the limits after every round of selection. I did an implementation before where I considered all the combinations of durations that can be created with a given candidate, and filtered out that candidate if none of those combinations would satisfy the limits. However, this proved to be too expensive computationally because the number of combinations grows exponentially.
I am wondering if anyone has any ideas about has any ideas about how this problem can be approached, or if it solvable at all.
Thanks!