Home | Contact Us | FAQ | Search & Site Map | Link to Us
Sign In | Join | Other 45 Sites in Network
Home
DiscussionsAccessExcelInfoPathOutlookPowerPointPublisherWord
DirectoryUser Groups
Related Topics
Outlook ExpressInternet ExplorerWindowsMS Server ProductsMore Topics ...

MS Office Forum / Excel / New Users / October 2007

Tip: Looking for answers? Try searching our database.

know the solution- find the operations?

Thread view: 
Enable EMail Alerts  Start New Thread
Thread rating: 
MDBJ - 04 Oct 2007 02:50 GMT
I have an old checkbook/billing issue.

I'm trying to figure a combination of billing amounts that equal an amount
that was paid.

simple terms, lets say there were vaild bills outstanding in the amount of
1,1,2,2,4,4,4,4,6,6,8

lets say there was a payment of 20$

how can I test every possible combination of my bills, including shorter
then all outstanding bills
so I do want
4+4+4+8  and
6+6+8 and
8+2+2+4+4  all to show up--

the actual #'s involved I need to find are more complex, decimals, but some
do repeat

I need a suggestion as to how to test all addition possibilities for my
outstanding invoices at the time I recieved a payment..  any pointers?
Bernie Deitrick - 04 Oct 2007 14:25 GMT
Below is the code from Harlan Grove.  Follow the instructions at the top concerning references, and
then run FindSums.  Note that it can take a looong time, depending on how many numbers you have.  It
will insert a new sheet with possilbe solutions.

HTH,
Bernie
MS Excel MVP

Option Explicit
'This *REQUIRES* VBAProject references to
 'Microsoft Scripting Runtime
 'Microsoft VBScript Regular Expressions 1.0
 'Written by Harlan Grove

Sub FindSums()
 Const TOL As Double = 0.000001  '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

 re.Global = True
 re.IgnoreCase = True

 On Error Resume Next

 Set x = Application.InputBox( _
   Prompt:="Enter range of values:", _
   Title:="findsums", _
   Default:="", _
   Type:=8 _
 )

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

 y = Application.InputBox( _
   Prompt:="Enter target value:", _
   Title:="findsums", _
   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:
 Application.EnableEvents = True
 Application.Calculation = xlCalculationAutomatic
 Application.StatusBar = False

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
   On Error Resume Next
   Set ws = ActiveWorkbook.Worksheets(OUTPUTWSN)

   If ws Is Nothing Then
     Err.Clear
     Application.ScreenUpdating = False
     Set ws = ActiveSheet
     Set r = Worksheets.Add.Range("A1")
     r.Parent.Name = OUTPUTWSN
     ws.Activate
     Application.ScreenUpdating = False

   Else
     ws.Cells.Clear
     Set r = ws.Range("A1")

   End If

   recsoln = 0

 ElseIf s = "" Then
   recsoln = r.Row - 1
   Set r = Nothing

 Else
   r.Value = s
   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
'---- end VBA code ----

>I have an old checkbook/billing issue.
>
[quoted text clipped - 16 lines]
> I need a suggestion as to how to test all addition possibilities for my outstanding invoices at
> the time I recieved a payment..  any pointers?
Dana DeLouis - 04 Oct 2007 18:17 GMT
>   Note that it can take a looong time, depending on how many numbers you
> have.

As a side note, I've always found it interesting how many solutions there
usually are.
As a small example, suppose one had the unique numbers 1-27, and asked how
many combinations equal 189.
It's hard to believe there are 1,265,204
If you had the numbers 1-30, and asked how many total 232, it jumps to
8,679,280

Signature

Dana DeLouis

> Below is the code from Harlan Grove.  Follow the instructions at the top
> concerning references, and then run FindSums.  Note that it can take a
[quoted text clipped - 257 lines]
>> I need a suggestion as to how to test all addition possibilities for my
>> outstanding invoices at the time I recieved a payment..  any pointers?
Bernie Deitrick - 04 Oct 2007 18:28 GMT
Dana,

What I find even more interesting is the number of solutions to the problem of the 24 numbers below
summing to 44,007.32, 44,007.31, and 44,007.30  - try it.  With all the integers it makes sense -
increase one, decrease another, ad naseum, but for these it really is surprising.

483.34
758.06
852.67
1,494.61
1,806.25
1,842.28
2,070.88
2,130.14
2,913.33
3,946.90
3,957.38
4,154.26
4,504.18
4,831.08
5,083.52
5,092.55
5,121.39
5,824.48
6,361.67
6,835.00
6,875.09
6,898.54
8,662.80
10,854.69

Bernie
MS Excel MVP

>>   Note that it can take a looong time, depending on how many numbers you have.
>
[quoted text clipped - 261 lines]
>>> I need a suggestion as to how to test all addition possibilities for my outstanding invoices at
>>> the time I recieved a payment..  any pointers?
Harlan Grove - 04 Oct 2007 20:15 GMT
"Bernie Deitrick" <deitbe @ consumer dot org> wrote...
...
>What I find even more interesting is the number of solutions to
>the problem of the 24 numbers below summing to 44,007.32,
>44,007.31, and 44,007.30  - try it.  With all the integers it
>makes sense - increase one, decrease another, ad naseum, but for
>these it really is surprising.
...

It shouldn't be surprising. If this were simple, there'd be well known
algorithms to do it. There aren't, but there's LOTS of explanations
that there aren't precisely because there are so many combinations
that need to be checked. With N numbers, there are always 2^N-N-1
nontrivial combinations. Tiny percentages of such huge numbers are
themselves large numbers.

Rate this thread:






 
Sign In
Join
My Latest Posts
My Monitored Threads
My Blog
My Photo Gallery
My Profile
My Homepage

Start New Thread
Enable EMail Alerts
Rate this Thread



©2008 Advenet LLC   Privacy Policy - Terms of Use
This website includes both content owned or controlled by Advenet as well as content owned or controlled by third parties.