Given a set of integers, is there an easy way to find the highest combination that is less than or equal to a maximum?
For example given (3, 7, 5) and a target of 13 we'd want 7+3+3=13 (though 5+5+3 is also correct, we only need one solution). If we had (4, 6, 12) and a target of 7 the maximum would be 6.
I can't seem to work out a "nice" algorithm to handle this, is there anything obvious I'm missing?
No perfect way to solve it. Lots of imperfect solutions abound, and there's probably one that suits your needs somewhere out there...
Re:First Glance
vsergu on 2003-09-05T21:51:31
In the packing problem you can use each member of the set at most once. In this problem you can use a member multiple times. That probably doesn't make it easier, though.Re:First Glance
ethan on 2003-09-06T08:21:08
In the packing problem you can use each member of the set at most once. In this problem you can use a member multiple times. That probably doesn't make it easier, though.
Indeed, it doesn't. Actually it makes it harder.:-) Now you suddenly have no longer simple permutations but instead much more possibilities to combine numbers together. Re:First Glance
chaoticset on 2003-09-07T01:47:11
Ahh. Another lesson to myself in the dangers of taking a single glance and moving from there...
