To find a combination of numbers that equal a set amount?

  • Thread starter Thread starter Guest
  • Start date Start date
G

Guest

In Excel, I have a column of random dollar amounts. I also have a total
amount that I have to figure out which combination dollar amounts in the
column could equal my total amount.
 
If you are looking for a solution (Not necessarily the only one) to a subset of
a group of numbers that will add up to a target number, then this can often be
done quite simply with Solver.

Assuming range of numbers in A1:A30, add a set of 0s in B1:B30 and in say B31
put

=SUMPRODUCT(A1:A30*B1:B30)

Now do Tools / Solver / Set Target Cell 'B31' to 'value of' and put in your
target
number. Then, using the range selector under the 'By Changing cells' section,
select cells B1:B30 as the ones to change and hit enter which will take you back
to the first dialog box. Now hit the 'Add' button, and add the constraint that
B1:B30 must be 'bin' (Means binary as in 1 or 0, and it's one of the dropdowns,
so just hit the arrow and select 'bin') and just hit Solve. You MUST ensure
that in this example, when you add the 'bin' constraint range, you do not
inadvertantly include the formula cell B31, else you will get an error message
such as 'Binary Contsraint cell reference must include only adjustable cells'

Won't do any more than single solution, but for a Finance Dept that will often
suffice in this context.

If interested, the following link will give you a helpful tutorial at
http://www.solver.com/stepbystep.htm
and which walks you through an interesting scenario and explains what you can do
with the tool.

If you are going to look for more than one target number in the data, then with
that formula in say B31, in B32 type the target number, and in B33 put =B32-B31.
Now have Solver solve B33 = to 0 with the same constraints. Saves having to
change any values in Solver that way, just type what you want in B32.
 
Peo,

I guess that it is not possible to find all combinations thet add up to the
given value? Also not by means of VBA?

Jack.
 
I guess that it is not possible to find all combinations thet add up to the
given value? Also not by means of VBA?
Click to expand...

It entirely depends how big your column of numbers is. If you have 10
numbers for example, then there are 2^10 = 1024 potential solutions to
exhaustively check. That's a small enough number to do easily with some
programming.

If you have 100 numbers in the column you're looking at a number of solutions
like 1 followed by 30 zeros. That's a serious problem to try to solve
exhaustively on a PC. Theoretically doable if you devote a PC to it full
time for much longer than you'd be willing to do.

If you have 1000 numbers forget any possibility of an exhaustive search.

With some clever programming you could probably speed up the search for
solutions by a factor of 10 or 100, but that's an insignificant improvement
for large columns of numbers.


Bill -- (Remove KILLSPAM from my address to use it)
 
Bill,

What you said about the amount of numbers was also my concern. Of course
nobody in a good state of mind would like his PC to work day and night for a
week to solve something like that. But it is a challenge (in my point of
view) to make a program that would do the job for, let's say, 20 or 30
numbers.

I supposed that giving the 30 numbers a random sequence, to be refreshed
after each calculation, would be a possibility. I am afraid however that
this is not a really clever idea.

Besides, I do not have the knowledge nor the experience to do it.

Can you or anybody else help?

Jack.
 
What you said about the amount of numbers was also my concern. Of course
nobody in a good state of mind would like his PC to work day and night for a
week to solve something like that.
Click to expand...

(I was thinking more in terms of 100 years or more)

But it is a challenge (in my point of view) to make a program that would
do the job for, let's say, 20 or 30 numbers.
Click to expand...

Well, 20 numbers have potentially 1 million solutions to search. 30 numbers
have about a billion. Either way it's more than you want to do with Excel,
and would instead want to use some much faster executing compiled programming
language like Fortran or C or some such.

The basic approach is simple if you want to pursue it as a challenge. You
sort of need to follow Ken Wright's approach. For 20 numbers you also create
a 20 bit binary number, starting from 0. Add up each of your numbers that
have a corresponding "1" in the binary number until the sum exceeds your
target sum, or you run out of numbers without reaching the target. Then you
iterate your binary number by 1 and do the whole thing over -- and over, and
over.

With some clever programming you could speed this up significantly for 20
numbers, but you'd still never be clever enough to do it exhaustively for 50
or 100 numbers. Ignoring of course pathological cases like where all the
numbers are somehow related, or all zero or some such where there could be
algorithms other than exhaustive searching.

Bill -- (Remove KILLSPAM from my address to use it)
 
Back
Top