Tell me more ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.
up vote 1 down vote favorite

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?

share|improve this question

2 Answers

up vote 4 down vote accepted

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.

share|improve this answer
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. – 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
up vote 0 down vote

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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