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?

2 Answers 2


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.

  • 2
    It'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:


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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.