software

I am with you on the brute force requirement, but there are a couple of
tricks to minimize the permiutations and combinations. By sorting the list of
input values you can determine to stop testing certain combinations knowing
that certain solutions can not be possible because they are going to be too
large. That is where the code that I posted is very good. I had some other
code that did almost exactly what you were suggesting but it was far slower.
From what I have seen Harlan's code is hard to beat. That being said the list
you are searching should be at most 25 or 30 entries.
--
HTH...

Jim Thomlinsonquot;Bill Martinquot; wrote:

gt; wrote:
gt; gt; Hello,
gt; gt;
gt; gt; I have a list of numbers in a column and I need to find which numbers
gt; gt; when summed together equal a figure. I have a list of invoice amounts
gt; gt; that I need to match up with payments (the payments are always made for
gt; gt; several invoices so I need to come up with sums of several invoices to
gt; gt; get to this payment amount).
gt; gt;
gt; gt; An example would be I have this in the following section (A1:A10):
gt; gt; $17,213.82
gt; gt; $4,563.02
gt; gt; $85,693.42
gt; gt; $1,166.01
gt; gt; $725.90
gt; gt; $580.09
gt; gt; $2,243.75
gt; gt; $240.16
gt; gt; $207.70
gt; gt; $725.90
gt; gt;
gt; gt; I need to find which combination of these figures would sum $1,173.76.
gt; gt;
gt; gt; Thanks in Advance,
gt; gt; Dza the troubled accountant
gt; gt;
gt;
gt; -----------------------------------
gt;
gt; I don't believe there is a simple, closed form solution to this problem. What
gt; you have to do is to exhaustively try all possible combinations to see which one
gt; (or *ones*) add up to what you want. This is possible to do with small problems
gt; like the example you've shown, but if there are a quot;largequot; number of entries it
gt; will take computer time in excess of the age of the universe to calculate. With
gt; 100 entries for example, the number of combinations you'd have to test 1.27
gt; times ten to the 30th power -- a *really* big number. With 20 entries you'd
gt; quot;onlyquot; have about one million combinations to check.
gt;
gt; What I would do is add an extra column of only 0 and 1 vales which represents a
gt; binary word in aggregate. Then multiply that column by your dollar values and
gt; sum them. This gives you the what that particular combination adds up to. Then
gt; you need to increment the binary word by one and do it again ... and again.
gt; Until you've tested all combinations.
gt;
gt; You're going to need a VBA macro to make this work. I don't think you can do it
gt; with simple formulas.
gt;
gt; Good luck...
gt;
gt; Bill
gt;

You're right, Jim, the OP could reduce his solution space by
disregarding the numbers greater than his quot;targetquot; number. In an
accounting environment, however, debits and credits (positive as well
as negative) may need to be considered- the negative numbers may react
with the positive larger numbers to arrive at the correct solution.I do agree that Harlan's code looks good. I haven't tried to compile and run
it, but it looks like a good approach.

Bill
------------------------------
Jim Thomlinson wrote:
gt; I am with you on the brute force requirement, but there are a couple of
gt; tricks to minimize the permiutations and combinations. By sorting the list of
gt; input values you can determine to stop testing certain combinations knowing
gt; that certain solutions can not be possible because they are going to be too
gt; large. That is where the code that I posted is very good. I had some other
gt; code that did almost exactly what you were suggesting but it was far slower.
gt; From what I have seen Harlan's code is hard to beat. That being said the list
gt; you are searching should be at most 25 or 30 entries.

Use Google's group search: groups.google.com/advanced_group_search

, look in Groups *excel*, with all of the words Add up numbers, Author
Harlan (yes, indeed, Harlan Grove)
and you'll find a discussion and very advanced solutions about this subject

--
Kind regards,

Niek Otten

quot;Dave Oquot; gt; wrote in message ups.com...
gt; You're right, Jim, the OP could reduce his solution space by
gt; disregarding the numbers greater than his quot;targetquot; number. In an
gt; accounting environment, however, debits and credits (positive as well
gt; as negative) may need to be considered- the negative numbers may react
gt; with the positive larger numbers to arrive at the correct solution.
gt;
Sorry, I missed that it had already been mentioned here

--
Kind regards,

Niek Otten

quot;Niek Ottenquot; gt; wrote in message
...
gt; Use Google's group search:
gt; groups.google.com/advanced_group_search
gt;
gt; , look in Groups *excel*, with all of the words Add up numbers, Author
gt; Harlan (yes, indeed, Harlan Grove)
gt; and you'll find a discussion and very advanced solutions about this
gt; subject
gt;
gt; --
gt; Kind regards,
gt;
gt; Niek Otten
gt;
gt; quot;Dave Oquot; gt; wrote in message
gt; ups.com...
gt;gt; You're right, Jim, the OP could reduce his solution space by
gt;gt; disregarding the numbers greater than his quot;targetquot; number. In an
gt;gt; accounting environment, however, debits and credits (positive as well
gt;gt; as negative) may need to be considered- the negative numbers may react
gt;gt; with the positive larger numbers to arrive at the correct solution.
gt;gt;
gt;
gt;
That is not quite what the code does. What it does is it sorts the original
values lowest to highest. Negatives will obviously be the lowest values. When
it is doing the combinations it moves in the direction of adding the next
highest number. If the combination exceeds the target value then it abandons
moving to the following next highest value because it obviously is not a
possible solution. I am not sure that I explained that very well but sufice
it to say that it works and it speeds up the execution by potentially a few
orders of magnitude.
--
HTH...

Jim Thomlinsonquot;Dave Oquot; wrote:

gt; You're right, Jim, the OP could reduce his solution space by
gt; disregarding the numbers greater than his quot;targetquot; number. In an
gt; accounting environment, however, debits and credits (positive as well
gt; as negative) may need to be considered- the negative numbers may react
gt; with the positive larger numbers to arrive at the correct solution.
gt;
gt;