MS Office Forum / Excel / New Users / October 2007
know the solution- find the operations?
|
|
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.
|
|
|