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
    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
    "not easy" == NP-Complete2010-12-14