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?
Add a comment
|
2 Answers
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.
-
2It's a special case of the knapsack problem where the value of each item is equal to its weight. Since it is a special case, it is not entirely unreasonable to expect that there might also be a special algorithm which is not in NP. Commented Sep 24, 2012 at 8:56
-
@JörgWMittag, this special case is one of the original NP-complete problems. Commented Sep 24, 2012 at 12:47
An example of your problem as I understand it is that you have numbers:
1,2,7,22,199,3,5,6,12
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:
1,2,3,5,6,7,12,22,199
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.
