I have a problem that boils to down having a set of integers and wanting the subset of those integers whose sum is closest to some target without going over. What's a good algorithm for doing this? Maybe it's even a well known problem whose name I don't know?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
It's the "Knapsack Problem" and is quite well known. Efficient algorithms are difficult as the problem is NP-Complete. This means you are not guaranteed a polynomial time solution for all cases of the problem though some algorithms do exist to solve it. They just do so rather slowly.
An example of your problem as I understand it is that you have numbers:
and you want a subset such that the sum of the numbers in the subset selected is larger than 17.
A simple approach would be to sort the input first to get:
now start adding until the sum > 17
you would have added enteritis 0,1,2,3,4,5,6 of the above array, those enteritis represent subset satisfying your criteria. However, for a set of inputs, the solution may not exist at all or there may be many solutions.