What algorithm should I use to find the closest solution to a given total using a list of integers?

Question

My problem is this:

Let's say I have an arbitrary list of integers A[2013, 54, 3, 32 1, 23...]

What is the best strategy to find which of those numbers I should add together to have a sum equal or closest to a given number ?

Obviously there is always the brute force method but I'm interested in knowing if there is a more optimised one.

Answer 1

When packing luggage into a car, you put the biggest items in first and then fit the smaller items around them. By analogy, a heuristic approach to your problem is to start with the member of your set that is as large as possible while still being smaller than your target. Then repeat the process for the difference between you current total and your target, and so on. This is known as a greedy algorithm.

For example, if your set is $\{2,3,5,8,13,21, 34\}$ and you target is $32$, start with $21$ (the largest value less than $32$), then add $8$ (because this is the large value less than $32-21=11$), and then add $3$.

A greedy algorithm is quick and simple, but will not always give you the best solution. For example, if your set is $\{1, 5, 23, 26\}$ and you target is $30$ then the greedy algorithm gives $26+1=27$, whereas the best solution is $23+5+1=29$.

Answer 2

The problem is NP-complete, but polynomial in the value of the given number, with a quite low polynomial degree. It's only difficult if the numbers involved are large.

Sorting from smallest to largest and adding until no number fits is not very clever, because it will likely be a rather large number that doesn't fit, and you won't get close to the desired sum. Much better to sort from largest to smallest and add the largest numbers first.

Now if you have items with a sum close to S, you can try to improve this. For example if your sum is too small by 117, but the smallest unused item is 317, you'd try if you have an item X in your list, and an item Y not in the list, where Y is about 200 smaller than X - swap X against Y, add the item of size 317. Even a simple algorithm will likely find you good improvements.

A completely different method: Let the desired sum be S, with a very large S (like many trillions). Then you can choose an s' say around 1,000,000, multiply all numbers involved by (s' / S), find items with a sum close to 1,000,000, and then pick the original items. Try for a few sums that are close to 1,000,000.

Answer 3

Thanks to @Yuval 's comment I was led to the Knapsack Problem which is exactly what I was looking for.

Although I did not understand much of the solutions proposed to this NP-complete problem in Wikipedia, I thought of a fast but totally unreliable approach:

Just sort the list of available integers from smallest to largest and start adding them until the desired condition is met.

I think that if all differences between two members of the integer set do not vary much then this approach is probably going to give the best and only solution.