Looking for a solution to find a sum of numbers in the given series which is closest to the number i specify?

Question

say i have a given set of numbers ( any numbers positive or negative). i now specify a number X. what i want is a solution to find the sum of numbers in the given series which is closest to the number i have specified. the solution should give me two numbers. one on the lower side which is closest to the specified number and one on the higher side. say i specify 500 then the solution should give a number say 480 which is on the lower side and 550 which may be on the higher side.

i am actually trying to build a code for this in VB. but this problem somehow eludes me.

Answer 1

The first half of your problem is the subset sum problem. Unfortunately, this is a difficult problem to solve in the general case, but if you only have to do this with a small set of numbers, you can find an answer.
http://en.wikipedia.org/wiki/Subset_sum_problem
I'm not sure how you get your second number, I think you could tweak the algorithm to look for an answer from the other direction.

Do you want code, or just theoretical solution? Is there a specific application you have in mind.

Let me give you the pieces first, I need to dig around and see if I have my code for this problem. Assuming you have N elements, you will need to store these in an array. You will need another array of N boolean values. Write a function that takes these two arrays and sums the N elements who have their corresponding value as TRUE in the boolean array. Essentially, this is a vector dot product of the 2 arrays. Now, you will need to generate all permutations of true/false values for this boolean array. If you are comfortable with writting recursive code that will be the easiest way to do this. This is doing a brute force test of all the combinations of numbers. With each test, if you find a number that sums closer to your previous best sum (either above or below your target depending on what you want) record the best sum and its corresponding boolean array. Continue this until all permutations have been exhausted. I know there are slightly better ways of doing this, but nothing is very efficient. This problem belongs to the NP-Complete problem set.

Here is some psuedo code, don't know VB very well:
boolean bools[n] 'Initialize to false
integer numbers[n] 'Initialize to your numbers
boolean bestPermuation[n]
best = 0
target = 500 'Or whatever you want


Sub Main
'Read in the numbers and target

Explore(numbers, bools, 0)

'Print out best and bestPermutation
End Sub


Sub Eval(numbers[n], bools[n])
sum = 0
for i=1 to N
if bools[i] then
sum = sum + numbers[i]
end if
next i

Eval = sum
End Sub

Sub Explore(numbers[n], bools[n], index)
test = Eval(numbers, bools)

' Change the line below to test > target for the other answer
if(test > best AND test < target) Then
best = test
bestPermutation = bools
end if

if(index + 1 <= n) Then
bools[index + 1] = true
Explore(numbers, bools, index + 1)
bools[index + 1] = false
Explore(numbers, bools, index + 1)
end if
End Sub

Answer 2

If the series has a closed form, then what you are looking for is the inverse of that form.
For example
N = ∑1 + 2 + 3 + 4 + 5 + ... + n = n(n + 1)/2
n^2 + n - 2N = 0
n = Int((-1 ±√(1 + 8N))/2) will give you the smaller value, and n + 1 will give you the larger value.

Answer 3

I don't know a general method to do this. About 20 years ago I ran a program in elementary BASIC which did it on a small, primitive computer, but I don't even remember how the program worked. Useful answer, eh?

PS. I don't think Helmut's answer cuts it either. or have I misunderstood?