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 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?

share|improve this question
1  
I guess this is similar to the subset sum problem: en.wikipedia.org/wiki/Subset_sum_problem –  PEV Jan 26 '11 at 19:26
    
Here is a similar question: stackoverflow.com/questions/2070359/… –  PEV Jan 26 '11 at 19:28
    
Exact copy by same person: stackoverflow.com/questions/4808503/series-calculation –  Aryabhata Jan 26 '11 at 23:21

2 Answers 2

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.