Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm developing a computer program, and need an algorithm to solve the following problem:

How to select the optimum combination of numbers from a random list that add to up to a certain total (or as close to as possible).

Example:

List of random numbers:

1.0, 2.1, 5.3

Required number = 6.5

Here the answer would be 6.3 (from 5.3 + 1.0) I believe.

The program needs to be able to operate on much bigger number sets.

I have some maths qualifications (up to a-level), but not expert, so if you could temper your respose to my level if possible, that would be appreciated!

share|improve this question
    
I'm assuming you don't want a brute-force solution? –  J. M. Dec 14 '10 at 14:15
    
Having now defined the proper terminology for my problem, brute force may be ok as the number of variables is relatively small. –  bombdefused Dec 14 '10 at 14:28
    
If so, it shouldn't be too hard to systematically enumerate length-k subsets, total them, and check that the difference of said sum from the target value is within a specified tolerance... –  J. M. Dec 14 '10 at 15:01
    
I think something that I should have said in my question, is that each number can be selected more than once. My algorithm at the moment is looking like it will just have to apply random operations while keeping track of the best solution so far. –  bombdefused Dec 14 '10 at 15:41
    
Why be random when you can be systematic? This is a computer program we are talking about, and as you have said, the space of variables is small... –  J. M. Dec 14 '10 at 16:05

2 Answers 2

up vote 0 down vote accepted

As Ross Millikan notes, this is a standard Subset Sum or Number Partition Problem which are both NP-Complete.

If your Subset Sum instance is $(a_0, a_1, \dots, a_{n-1})$, where each $a_k \in \mathbb{Z}$, and the numbers in the list are small compared with the list size (i.e. $\log_2 ( \max(a_k) ) << n$), then you can either use some brute force search, as in the Complete Karmarkar Karp algorithm (a review of which can be found here) or some dynamic programming method (this for example).

You can always create an instance of Subset Sum/Number Partition out of a list that has it's numbers drawn from the reals by multiplying each element in the list by some large number to make it integer (for example, multiplying each number in your above list by 10 would turn this into a standard Subset Sum/Number Partition Problem).

Being NP-Complete means, in general, this problem is probably hard, in that there is nothing better than an exponential/brute force approach. Not all brute force algorithms are created equal, though, and depending on what your needs are, you might find a better algorithm suited to the particular type of Subset Sum/Number Partition Problem instances you're creating.

Some researchers have had some luck with lattice reduction techniques, so that's another avenue of attack, though lattice reduction techniques (LLL and PSLQ for example) are a bit advanced and, from my understanding, don't fare all that well for Subset Sum/Number Partition Problem instances past a certain size.

share|improve this answer
    
Thanks for a comprehensive answer. –  bombdefused Dec 16 '10 at 9:55

This is close to the subset sum problem, which is not easy. But some approaches are in the Wikipedia article. The section on the approximate algorithm seems quite applicable.

share|improve this answer
    
Thanks for this. I'll read up. –  bombdefused Dec 14 '10 at 14:27
1  
"not easy" meaning here: We know no algorithm with polynomial runtime. –  Raphael Dec 14 '10 at 15:38
    
"not easy" == NP-Complete –  user4143 Dec 14 '10 at 16:10

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.