# Subset whose sum gets closest to saturating some bound

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

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.

• 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. – Jörg W Mittag Sep 24 '12 at 8:56
• @JörgWMittag, this special case is one of the original NP-complete problems. – Peter Taylor Sep 24 '12 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.