find sum in list of of numbers

D

dvpetta

Hello,

I have a list of numbers in a column and I need to find which numbers
when summed together equal a figure. I have a list of invoice amounts
that I need to match up with payments (the payments are always made for
several invoices so I need to come up with sums of several invoices to
get to this payment amount).

An example would be I have this in the following section (A1:A10):
$17,213.82
$4,563.02
$85,693.42
$1,166.01
$725.90
$580.09
$2,243.75
$240.16
$207.70
$725.90

I need to find which combination of these figures would sum $1,173.76.

Thanks in Advance,
Dza the troubled accountant
 
J

Jim Thomlinson

Here is some code. Note that you need to create references to a couple of
librarys in order tom make this code work (In VBE select Tools ->
References).

'Microsoft Scripting Runtime
'Microsoft VBScript Regular Expressions 1.0 or higher

This code should be placed in a standard module...

Option Explicit
' Original solution created by
' Harlan Grove

Public Sub FindSums()
'This *REQUIRES* VBAProject references to
'Microsoft Scripting Runtime
'Microsoft VBScript Regular Expressions 1.0 or higher

Const TOL As Double = 0.0001 'modify as needed
Dim c As Variant

Dim j As Long, k As Long, n As Long, p As Boolean
Dim s As String, t As Double, u As Double
Dim v As Variant, x As Variant, y As Variant
Dim dc1 As New Dictionary, dc2 As New Dictionary
Dim dcn As Dictionary, dco As Dictionary
Dim re As New RegExp
Dim wks As Worksheet
Application.EnableCancelKey = xlErrorHandler

re.Global = True
re.IgnoreCase = True

On Error Resume Next

Set wks = ActiveSheet
Set x = Intersect(Selection, wks.UsedRange)

If x Is Nothing Then
Err.Clear
Exit Sub
End If

y = Application.InputBox( _
Prompt:="Enter target value:", _
Title:="Find Sums", _
Default:="", _
Type:=1 _
)

If VarType(y) = vbBoolean Then
Exit Sub
Else
t = y
End If

On Error GoTo 0

Set dco = dc1
Set dcn = dc2

Call recsoln

For Each y In x.Value2
If VarType(y) = vbDouble Then
If Abs(t - y) < TOL Then
recsoln "+" & Format(y)

ElseIf dco.Exists(y) Then
dco(y) = dco(y) + 1

ElseIf y < t - TOL Then
dco.Add Key:=y, Item:=1

c = CDec(c + 1)
Application.StatusBar = "[1] " & Format(c)

End If

End If
Next y

n = dco.Count

ReDim v(1 To n, 1 To 3)

For k = 1 To n
v(k, 1) = dco.Keys(k - 1)
v(k, 2) = dco.Items(k - 1)
Next k

qsortd v, 1, n

For k = n To 1 Step -1
v(k, 3) = v(k, 1) * v(k, 2) + v(IIf(k = n, n, k + 1), 3)
If v(k, 3) > t Then dcn.Add Key:="+" & _
Format(v(k, 1)), Item:=v(k, 1)
Next k

On Error GoTo CleanUp
Application.EnableEvents = False
Application.Calculation = xlCalculationManual

For k = 2 To n
dco.RemoveAll
swapo dco, dcn

For Each y In dco.Keys
p = False

For j = 1 To n
If v(j, 3) < t - dco(y) - TOL Then Exit For
x = v(j, 1)
s = "+" & Format(x)
If Right(y, Len(s)) = s Then p = True
If p Then
re.Pattern = "\" & s & "(?=(\+|$))"
If re.Execute(y).Count < v(j, 2) Then
u = dco(y) + x
If Abs(t - u) < TOL Then
recsoln y & s
ElseIf u < t - TOL Then
dcn.Add Key:=y & s, Item:=u
c = CDec(c + 1)
Application.StatusBar = "[" & Format(k) & "] " & _
Format(c)
End If
End If
End If
Next j
Next y

If dcn.Count = 0 Then Exit For
Next k

If (recsoln() = 0) Then _
MsgBox Prompt:="All combinations exhausted.", _
Title:="No Solution"

CleanUp:
If Err = 18 Then
If MsgBox("Do you want to stop searching?", vbYesNo, "Quit?") = vbYes Then
Application.StatusBar = False
Application.EnableEvents = True
Application.Calculation = xlCalculationAutomatic
Application.StatusBar = False
End
Else
Resume
End If
Else
Application.EnableEvents = True
Application.Calculation = xlCalculationAutomatic
Application.StatusBar = False
End If
End Sub

Private Function recsoln(Optional s As String)
Const OUTPUTWSN As String = "Findsums Solutions" 'modify to taste

Static r As Range
Dim ws As Worksheet

If s = "" And r Is Nothing Then
If Not SheetExists(OUTPUTWSN, ActiveWorkbook) Then
Application.ScreenUpdating = False
Worksheets.Add Before:=ActiveSheet
Set ws = ActiveSheet
ws.Name = OUTPUTWSN
ws.Cells.NumberFormat = "#,##0.00"
Set r = ws.Range("A2")
Else
Set ws = Sheets(OUTPUTWSN)
ws.Cells.Clear
ws.Cells.NumberFormat = "#,##0.00"
Set r = ws.Range("A2")
End If
recsoln = 0
ElseIf s = "" Then
recsoln = r.Row - 1
Set r = Nothing
Else
Call PostAnswers(s, r)
Set r = r.Offset(1, 0)
recsoln = r.Row - 1
End If
End Function

Private Sub qsortd(v As Variant, lft As Long, rgt As Long)
'ad hoc quicksort subroutine
'translated from Aho, Weinberger & Kernighan,
'"The Awk Programming Language", page 161

Dim j As Long, pvt As Long

If (lft >= rgt) Then Exit Sub
swap2 v, lft, lft + Int((rgt - lft + 1) * Rnd)
pvt = lft
For j = lft + 1 To rgt
If v(j, 1) > v(lft, 1) Then
pvt = pvt + 1
swap2 v, pvt, j
End If
Next j

swap2 v, lft, pvt

qsortd v, lft, pvt - 1
qsortd v, pvt + 1, rgt
End Sub

Private Sub swap2(v As Variant, i As Long, j As Long)
'modified version of the swap procedure from
'translated from Aho, Weinberger & Kernighan,
'"The Awk Programming Language", page 161

Dim t As Variant, k As Long

For k = LBound(v, 2) To UBound(v, 2)
t = v(i, k)
v(i, k) = v(j, k)
v(j, k) = t
Next k
End Sub

Private Sub swapo(a As Object, b As Object)
Dim t As Object

Set t = a
Set a = b
Set b = t
End Sub

Private Sub PostAnswers(ByVal strValue As String, ByVal rng As Range)
Dim aryCSVValues As Variant
Dim intCounter As Integer

aryCSVValues = Split(Mid$(strValue, 2, Len(strValue)), "+")
For intCounter = LBound(aryCSVValues) To UBound(aryCSVValues)
rng.Value = aryCSVValues(intCounter)
Set rng = rng.Offset(0, 1)
Next intCounter
End Sub
 
D

Dave O

The answer is:
$725.90
$240.16
$207.70

I've written a program that applies a brute force approach to the task-
it checks every possible combination of the "pool" of numbers to arrive
at the target total. The brute force idea works for comparatively
small pools, but since the number of possible combinations doubles with
each additional pool member the processing time increases
commensurately. One poster to this newsgroup wanted to process a list
of 100 numbers, which amounts to
1,267,650,600,228,230,000,000,000,000,000 possible combinations and
would require the resources of a major government (or maybe just the
NSA) to process.

How many of these do you have? I don't mind doing a few for you.
 
B

Bill Martin

Hello,

I have a list of numbers in a column and I need to find which numbers
when summed together equal a figure. I have a list of invoice amounts
that I need to match up with payments (the payments are always made for
several invoices so I need to come up with sums of several invoices to
get to this payment amount).

An example would be I have this in the following section (A1:A10):
$17,213.82
$4,563.02
$85,693.42
$1,166.01
$725.90
$580.09
$2,243.75
$240.16
$207.70
$725.90

I need to find which combination of these figures would sum $1,173.76.

Thanks in Advance,
Dza the troubled accountant

-----------------------------------

I don't believe there is a simple, closed form solution to this problem. What
you have to do is to exhaustively try all possible combinations to see which one
(or *ones*) add up to what you want. This is possible to do with small problems
like the example you've shown, but if there are a "large" number of entries it
will take computer time in excess of the age of the universe to calculate. With
100 entries for example, the number of combinations you'd have to test 1.27
times ten to the 30th power -- a *really* big number. With 20 entries you'd
"only" have about one million combinations to check.

What I would do is add an extra column of only 0 and 1 vales which represents a
binary word in aggregate. Then multiply that column by your dollar values and
sum them. This gives you the what that particular combination adds up to. Then
you need to increment the binary word by one and do it again ... and again.
Until you've tested all combinations.

You're going to need a VBA macro to make this work. I don't think you can do it
with simple formulas.

Good luck...

Bill
 
R

Ron Coderre

Have you tried using Excel Solver

First a little prep work....

A1:A1 (your list of values)
B1:B10 (leave blank)
C1: =A1*B1
(copy that fomula down through C10

C11: =SUM(C1:C10)

Now to use Solver....
Tools>Solver
Set Cell: C11
Equal to the Value of: 1173.76
By Changing Cells: B1:B10
Subject to the Constraints....
(click the add button and constrain B1:B10 to Binary)
Click [OK]
Click [Solve]

Excel will toggle cells B1:B10 between 1 and 0 until it comes up with a
combination that sums to 1,173.76

Does that help?

***********
Regards,
Ron

XL2002, WinXP-Pro
 
B

Bill Martin

I do like your Solver approach -- I hadn't thought of that. Given that this is
an Accounting problem though, how would one get Solver to identify multiple
solutions to the problem when they exist? If you're trying to match invoices
you'd like to know that you're matching them correctly -- not just *possibly*
correctly. Which requires a person to stare at *all* the various possible
solutions and decide which one is most likely given some knowledge of the
customers involved and what they've ordered in the past, etc.

For example, take the list of 10 values that Dza provided and use them all twice
to make 20 entries. Now there are 8 valid solutions, but Solver only seems to
find one and stops.

Personally, I think you need VBA for this problem but I'm open to education...

Bill
----------------------------------
Ron said:
Have you tried using Excel Solver

First a little prep work....

A1:A1 (your list of values)
B1:B10 (leave blank)
C1: =A1*B1
(copy that fomula down through C10

C11: =SUM(C1:C10)

Now to use Solver....
Tools>Solver
Set Cell: C11
Equal to the Value of: 1173.76
By Changing Cells: B1:B10
Subject to the Constraints....
(click the add button and constrain B1:B10 to Binary)
Click [OK]
Click [Solve]

Excel will toggle cells B1:B10 between 1 and 0 until it comes up with a
combination that sums to 1,173.76

Does that help?

***********
Regards,
Ron

XL2002, WinXP-Pro


:

The answer is:
$725.90
$240.16
$207.70

I've written a program that applies a brute force approach to the task-
it checks every possible combination of the "pool" of numbers to arrive
at the target total. The brute force idea works for comparatively
small pools, but since the number of possible combinations doubles with
each additional pool member the processing time increases
commensurately. One poster to this newsgroup wanted to process a list
of 100 numbers, which amounts to
1,267,650,600,228,230,000,000,000,000,000 possible combinations and
would require the resources of a major government (or maybe just the
NSA) to process.

How many of these do you have? I don't mind doing a few for you.
 
D

Dave O

Bill makes a good point- I wrote my original program to find "the"
solution and then stop, but one day on a whim I allowed it to cycle
through the rest of the combinations and found multiple answers to the
problem. Since then re-wrote my program to show all possible
solutions, and frequently find more than one correct answer to the
problem.

Still haven't heard from the OP yet!
 
J

Jim Thomlinson

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.
 
R

Ron Coderre

Solver isn't a panacea....It's just a nice shortcut for relatively simple
situations without having to find or write code. However, if solver finds
one acceptable solution....couldn't we just create another "flag" field to
prevent the same value from being used more than once?

Regarding professional accounting/financial environments, I would hope that
proper internal controls would prevent the situation where a large number of
invoices/checks/whatever would have to be matched (trial and error) against
an amount. Of course there's always the customer who sends a massive check
paying some unknown combination of invoices. Consequently, for those
instances, a phone call to the payee should clear up the confusion
definitively. You wouldn't want to just guess, right?

If a large, multi-solution, iteratave approach cannot be avoided
though....You're right, a vba program would be the way to go.


***********
Regards,
Ron

XL2002, WinXP-Pro


Bill Martin said:
I do like your Solver approach -- I hadn't thought of that. Given that this is
an Accounting problem though, how would one get Solver to identify multiple
solutions to the problem when they exist? If you're trying to match invoices
you'd like to know that you're matching them correctly -- not just *possibly*
correctly. Which requires a person to stare at *all* the various possible
solutions and decide which one is most likely given some knowledge of the
customers involved and what they've ordered in the past, etc.

For example, take the list of 10 values that Dza provided and use them all twice
to make 20 entries. Now there are 8 valid solutions, but Solver only seems to
find one and stops.

Personally, I think you need VBA for this problem but I'm open to education...

Bill
----------------------------------
Ron said:
Have you tried using Excel Solver

First a little prep work....

A1:A1 (your list of values)
B1:B10 (leave blank)
C1: =A1*B1
(copy that fomula down through C10

C11: =SUM(C1:C10)

Now to use Solver....
Tools>Solver
Set Cell: C11
Equal to the Value of: 1173.76
By Changing Cells: B1:B10
Subject to the Constraints....
(click the add button and constrain B1:B10 to Binary)
Click [OK]
Click [Solve]

Excel will toggle cells B1:B10 between 1 and 0 until it comes up with a
combination that sums to 1,173.76

Does that help?

***********
Regards,
Ron

XL2002, WinXP-Pro


:

The answer is:
$725.90
$240.16
$207.70

I've written a program that applies a brute force approach to the task-
it checks every possible combination of the "pool" of numbers to arrive
at the target total. The brute force idea works for comparatively
small pools, but since the number of possible combinations doubles with
each additional pool member the processing time increases
commensurately. One poster to this newsgroup wanted to process a list
of 100 numbers, which amounts to
1,267,650,600,228,230,000,000,000,000,000 possible combinations and
would require the resources of a major government (or maybe just the
NSA) to process.

How many of these do you have? I don't mind doing a few for you.
 
B

Bill Martin

They do presumably have controls. And I don't think people routinely match
invoices like this. However, contols fail, data gets lost, people do stupid
things. And them somehow you've got to clean up the mess.

Bill
 
D

Dave O

You're right, Jim, the OP could reduce his solution space by
disregarding the numbers greater than his "target" 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.
 
B

Bill Martin

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
 
H

Harlan Grove

Ron Coderre wrote...
Solver isn't a panacea....It's just a nice shortcut for relatively simple
situations without having to find or write code. However, if solver finds
one acceptable solution....couldn't we just create another "flag" field to
prevent the same value from being used more than once?

Perhaps. How would you do that since it's not one value but one
combination of values (OK, a vector of 1s and 0s that could be
considered a single vector value in {0,1}^N) that'd need to be
excluded. As I see it, you'd need to use a kludge like SUMPRODUCT of
the vector of 1s and 0s against 2^(ROW(INDIRECT("1:"&N))-1) to produce
unique identifiers for each solution, save them in a list, then use a
COUNTIF = 0 expression on that list with criteria equal to the current
SUMPRODUCT value. And you'd need to automate storing the idenifiers for
previous solutions, so VBA is unavoidable.
Regarding professional accounting/financial environments, I would hope that
proper internal controls would prevent the situation where a large number of
invoices/checks/whatever would have to be matched (trial and error) against
an amount. Of course there's always the customer who sends a massive check
paying some unknown combination of invoices. Consequently, for those
instances, a phone call to the payee should clear up the confusion
definitively. You wouldn't want to just guess, right?
....

In the real world, reconcilliation of different data sources that
should produce the same results is an unfortunate recurring problem.
And there's often no one to call to get a quick, simple answer.
If a large, multi-solution, iteratave approach cannot be avoided
though....You're right, a vba program would be the way to go.

Yup.
 
J

Jim Thomlinson

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.
 
J

Jim Thomlinson

When a customer sends you a check for $1,173.76 with no backup then you match
it the best you can. Been there and done that. They will need all possible
solutions because they will want to match to the oldest stuff first.

This kind of code is also very handy for doing year end working papers where
you need to reconcile the ending amount of a Balance Sheet account. Usually
you can match off the vast majority of the debits and credits but very often
you end up with a few entries that (because of reversels, reclassifications
and just plain weirdness) don't match easily. That is another place where
this kind of thing thing is handy.
--
HTH...

Jim Thomlinson


Ron Coderre said:
Solver isn't a panacea....It's just a nice shortcut for relatively simple
situations without having to find or write code. However, if solver finds
one acceptable solution....couldn't we just create another "flag" field to
prevent the same value from being used more than once?

Regarding professional accounting/financial environments, I would hope that
proper internal controls would prevent the situation where a large number of
invoices/checks/whatever would have to be matched (trial and error) against
an amount. Of course there's always the customer who sends a massive check
paying some unknown combination of invoices. Consequently, for those
instances, a phone call to the payee should clear up the confusion
definitively. You wouldn't want to just guess, right?

If a large, multi-solution, iteratave approach cannot be avoided
though....You're right, a vba program would be the way to go.


***********
Regards,
Ron

XL2002, WinXP-Pro


Bill Martin said:
I do like your Solver approach -- I hadn't thought of that. Given that this is
an Accounting problem though, how would one get Solver to identify multiple
solutions to the problem when they exist? If you're trying to match invoices
you'd like to know that you're matching them correctly -- not just *possibly*
correctly. Which requires a person to stare at *all* the various possible
solutions and decide which one is most likely given some knowledge of the
customers involved and what they've ordered in the past, etc.

For example, take the list of 10 values that Dza provided and use them all twice
to make 20 entries. Now there are 8 valid solutions, but Solver only seems to
find one and stops.

Personally, I think you need VBA for this problem but I'm open to education...

Bill
----------------------------------
Ron said:
Have you tried using Excel Solver

First a little prep work....

A1:A1 (your list of values)
B1:B10 (leave blank)
C1: =A1*B1
(copy that fomula down through C10

C11: =SUM(C1:C10)

Now to use Solver....
Tools>Solver
Set Cell: C11
Equal to the Value of: 1173.76
By Changing Cells: B1:B10
Subject to the Constraints....
(click the add button and constrain B1:B10 to Binary)
Click [OK]
Click [Solve]

Excel will toggle cells B1:B10 between 1 and 0 until it comes up with a
combination that sums to 1,173.76

Does that help?

***********
Regards,
Ron

XL2002, WinXP-Pro


:


The answer is:
$725.90
$240.16
$207.70

I've written a program that applies a brute force approach to the task-
it checks every possible combination of the "pool" of numbers to arrive
at the target total. The brute force idea works for comparatively
small pools, but since the number of possible combinations doubles with
each additional pool member the processing time increases
commensurately. One poster to this newsgroup wanted to process a list
of 100 numbers, which amounts to
1,267,650,600,228,230,000,000,000,000,000 possible combinations and
would require the resources of a major government (or maybe just the
NSA) to process.

How many of these do you have? I don't mind doing a few for you.
 
H

Harlan Grove

Jim Thomlinson wrote...
....
Private Sub PostAnswers(ByVal strValue As String, ByVal rng As Range)
Dim aryCSVValues As Variant
Dim intCounter As Integer

aryCSVValues = Split(Mid$(strValue, 2, Len(strValue)), "+")
For intCounter = LBound(aryCSVValues) To UBound(aryCSVValues)
rng.Value = aryCSVValues(intCounter)
Set rng = rng.Offset(0, 1)
Next intCounter
End Sub
....

This is your code. You should have indicated that. You also made a few
modifications in my original procedures. I don't have an issue with you
modifying my code, just with the lack of any way to distinguish your
code from mine.

Off-topic: I hate long variable names. There's a problematic case for
them in long, complex procedures, but other than typing exercise I
don't see the usefulness in short procedures. Ah, for programmers'
editors in which different colors could be assigned to variable tokens
of different types!

Back on-topic. My own code is at

http://groups.google.com/group/microsoft.public.excel/msg/7419858047398beb

Your comment in your other response in this thread is apt: N > 30 makes
for LONG execution times, but the macro works for larger N. I haven't
torture-tested it, but the large N with skewed values (median value
outside mean +/- 25%) will almost certainly exceed most PC's memory
resources, real and virtual. I have a test case with N=100 cells filled
with values generated by =ROUND(RAND()^-4,2), in the particular case 68
of 100 values < 100, and sought 5000 as the sum. There were 129
combinations of 1 to 6 values summing to 5000 and 464 of 7 (when I
cancelled the macro). Not sure how much information there might be if
there were more than 1 million combinations summing to 5000. How would
anyone choose which one to use?

In other words, the programming was an interesting exercise, but I
still don't believe it provides any value.
 
J

Jim Thomlinson

My appologies for not documenting where I had made modifications to your
code... As a professional courtesy I should have done that and I will
endevour to make the necessary notations at my end. Thanks for sharing your
work and once again I appoligize.

As for long variable names I have always favoured them purely from a
readability standpoint. I have debugged too much code written by others that
was almost impossible to follow. Not to mention it keeps things straight in
my head when I am writing it. Probably more the latter than the former... :)
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Top