0
$\begingroup$

I have some random integers separated by space read from a text file like

99 20 30 1 100 400 5 10 

I have to find a sum from any combination of these integers that is closest to a specifiq number like

183 

what is the fastest and accurate way of doing this?

  • 0
    Exact copy by same person: http://stackoverflow.com/questions/4808503/series-calculation2011-01-26

2 Answers 2

1

The non-trivial algorithm takes $2^{n/2}$ time and memory. Divide the list into two parts and calculate all the internal sums. Sort both lists, put one pointer at the low end of one list, and another at the high end of the other list. Advance the second pointer until the sum crosses the target. Then advance the first pointer, and repeat. Maintain the "best sum encountered so far", and once the first pointer is done traversing the list, you have the optimum in your hands.

This algorithm isn't really practical, and in practice you can probably do better, potentially depending on properties of the problem. Also, there are probably nice approximation algorithms that work well in practice.

1

You can also have a look at http://comeoncodeon.wordpress.com/2009/07/21/counting-problem/

Problem 1 describes different approaches to see whether a sum K is poosible. The DP approach for the Problem 1 should give you all the numbers that are possible sum of a subset. Then you can simply do search for the nearest.