Hello, I am working on a problem that would like for me to return the best sum of x numbers given a list of them, without exceeding a limit. The subset is a variable, so from a list { 12, 15, 30, 45 }, one iteration may ask to find the best sum of 2 of them such that it’s less than or equal to 44 (30 + 12), while another may be the best sum of 3 of them such that it’s less than or equal to 55, and so on. It can also return null if no such best sum exists.
The problem I’m having is figuring out how to iterate through the list such that it would compute each possible sum, given the subset. A similar problem I worked on involved a constant subset of 2, so I could use an outer and inner loop to cycle through.
So basically the function is supplied with a limit, a number indicating how many numbers to add together, and a list of numbers.
The task is pretty poorly defined, that’s what I can say.
Well, as far as I can tell, this problem here:
how to iterate through the list
Is known as “enumerating k-combinations”, if I understood it right. Can be done with this extention method:
Not the most efficient solution at all, but it will do the trick.
Not gonna dare digging in your overall problem, though.
Simplest solution is to enumerate all of the possible groups of size x, then calculate their sums, then take the ones lower than your limit ‘y’, then take the largest remaining value.
However, this can be endlessly optimised and that’s where the complexity really is.