1
$\begingroup$

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!

  • 0
    I'm assuming you don't want a brute-force solution?2010-12-14
  • 0
    Having now defined the proper terminology for my problem, brute force may be ok as the number of variables is relatively small.2010-12-14
  • 0
    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...2010-12-14
  • 0
    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.2010-12-14
  • 0
    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...2010-12-14

2 Answers 2

0

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.

  • 0
    Thanks for a comprehensive answer.2010-12-16
3

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.

  • 0
    Thanks for this. I'll read up.2010-12-14
  • 1
    "not easy" meaning here: We know no algorithm with polynomial runtime.2010-12-14
  • 0
    "not easy" == NP-Complete2010-12-14