mystery number solution

K

Keven

I have a number of values that are $s . I also have a sum of some of these
numbers. I need a formula to figure out which numbers add to my total. I do
not know how many numbers will equal my total. TIA
 
D

Dave O

I've written software that will do this. You have a column of numbers-
let's call it the pool- and a subset of numbers in the pool add up to
your sum. How many numbers are in your pool?
 
H

Henry

Keven,

I can't think of a mathematical answer to this, looks like a trial and error
type of thing.

My approach would be to sort your numbers into order.
Take the largest number away from your total and see if the remainder is
larger or the same as the smallest number.
If not, then the largest number can be discarded.
If it is larger than the smallest number, find the largest number that is
the same as or next smaller to your remainder.

Sounds complicated but an example might help!

Total =10
Numbers = 9,8,6,4,3.

Total - largest number 10-9=1
1 is smaller than the smallest number in the list so you can discard 9

Next try
Total - largest number 10-8=2
2 is smaller than the smallest number in the list so you can discard 8

Next try
Total - Largest number 10 - 6 = 4
4 is bigger than the smallest number in the list so:-
Look through the list for the number which is = to 4 or is the next smallest
4 is in the list, so you've found the answer.

You could use recursion to get the answer for more complex examples.

I have assumed that there is only one possible answer to each problem.
If there is more than one answer, this method would only find the first
solution.

I've never tried using recursion in VBA and don't even know if it's
possible.
I would have preferred to use a lower level language like C++ for this, even
though I'm less than fluent in it.

Hope that helps
Henry
 
J

joeu2004

Keven said:
I have a number of values that are $s . I also have a sum of some
of these numbers. I need a formula to figure out which numbers add
to my total. I do not know how many numbers will equal my total.
Click to expand...

In general, there is no closed-form formula for this -- only
alogithms. And of course, there can be multiple answers, unless
you restrict the solution space further (e.g, "find the largest
numbers that sum to the desired total"). In fact, it would be
good if you can restrict the solution space. Otherwise, the
algorithm must look at all possible sums of 1, 2, ... up to N
numbers. That can be a staggering number, depending on the size
of N (although some combinations will be truncated once an
overflow occurs).

I would not think Excel is the best tool for solving this problem,
although I guess VBA can be used to solve any problem that
requires a programming language.

(Hmm, does VBA support recursion?)
 
D

Dave O

My software- VBA based, no recursion- uses a brute force algorithm to
test every possible combination. joeu2...makes a very good point about
limiting the solution space: every time the number pool increases by
one, the number of combinations doubles.
 
Top