find numbers that total to a target, need examples

[partlycloudy22]

Does anyone have a list of numbers for which they need to find a set
that adds to a certain value? I am working on some code and would like
some real world examples to feed it.

For example, say I have the following list of numbers:

979.22
7047.06
10737.24
5533.48
11508.32
13852.8
3145.03
1914.74
3339.86
-3339.86
9055.51
-9055.51
1193.44
4305.22
2665.57
11996.98
4104.66
11257.6

I want to find the combination of numbers that add to $76,395.94.

Does anyone have any lists they could post for me to test the code
with? Long or short lists will work, and real world examples are
preferable. Thanks!

 

[CurlyDave]

Very strange request ??

 

[joeu2004]

Does anyone have a list of numbers for which they
need to find a set that adds to a certain value?

I am working on some code and would like some real
world examples to feed it.
[....]
I want to find the combination of numbers that add
to $76,395.94.

I'm going to go out on a limb and assert that no one will have list of
numbers, a subset of which should add up to exactly $76,395.94.

(Perhaps you mean to ask for a list and a goal __like__ $76,395.94.
Even so ....)

First, I would suggest that you relax your requirement. For example,
find the largest sum less than or equal to the goal ($76,395.94).

Second, I suggest that you create your own random lists. You might
want to place some reasonable constraints on the individual numbers,
and you probably want to be sure that each number is rounded to 2
decimal places.

(But if you "must" compare for equality, be sure to round the sum
before comparing. This is needed because of the way that Excel stores
values and performs arithmetic, relying on a standard binary
representation.)

Finally, I wonder if you realize the computational magnitude of the
problem as you stated it. For example, in your list, the number of
potential sums to evaluate is SUMPRODUCT(COMBIN(18,ROW($1:$18)) --
262,143. If someone gave you a list of more than 20 numbers, that
would be a lot of sums to compute and compare (over 1 million).

You might want to place some reasonable constraints on the size of
your lists and on the number (or maximum number) of values that
comprise the sum.

HTH.


----- original posting -----

 

[partlycloudy22]

Does anyone have a list of numbers for which they
need to find a set that adds to a certain value?

I am working on some code and would like some real
world examples to feed it.
[....]
I want to find the combination of numbers that add
to $76,395.94.

I'm going to go out on a limb and assert that no one will have list of
numbers, a subset of which should add up to exactly $76,395.94.

(Perhaps you mean to ask for a list and a goal __like__ $76,395.94.
Even so ....)

First, I would suggest that you relax your requirement.  For example,
find the largest sum less than or equal to the goal ($76,395.94).

Second, I suggest that you create your own random lists.  You might
want to place some reasonable constraints on the individual numbers,
and you probably want to be sure that each number is rounded to 2
decimal places.

(But if you "must" compare for equality, be sure to round the sum
before comparing.  This is needed because of the way that Excel stores
values and performs arithmetic, relying on a standard binary
representation.)

Finally, I wonder if you realize the computational magnitude of the
problem as you stated it.  For example, in your list, the number of
potential sums to evaluate is SUMPRODUCT(COMBIN(18,ROW($1:$18)) --
262,143.  If someone gave you a list of more than 20 numbers, that
would be a lot of sums to compute and compare (over 1 million).

You might want to place some reasonable constraints on the size of
your lists and on the number (or maximum number) of values that
comprise the sum.

HTH.

----- original posting -----

Does anyone have a list of numbers for which they need to find a set
that adds to a certain value? I am working on some code and would like
some real world examples to feed it.

For example, say I have the following list of numbers:

I want to find the combination of numbers that add to $76,395.94.

Does anyone have any lists they could post for me to test the code
with? Long or short lists will work, and real world examples are
preferable. Thanks!

 

[partlycloudy22]

Does anyone have a list of numbers for which they
need to find a set that adds to a certain value?

I am working on some code and would like some real
world examples to feed it.
[....]
I want to find the combination of numbers that add
to $76,395.94.

I'm going to go out on a limb and assert that no one will have list of
numbers, a subset of which should add up to exactly $76,395.94.

(Perhaps you mean to ask for a list and a goal __like__ $76,395.94.
Even so ....)

First, I would suggest that you relax your requirement.  For example,
find the largest sum less than or equal to the goal ($76,395.94).

Second, I suggest that you create your own random lists.  You might
want to place some reasonable constraints on the individual numbers,
and you probably want to be sure that each number is rounded to 2
decimal places.

(But if you "must" compare for equality, be sure to round the sum
before comparing.  This is needed because of the way that Excel stores
values and performs arithmetic, relying on a standard binary
representation.)

Finally, I wonder if you realize the computational magnitude of the
problem as you stated it.  For example, in your list, the number of
potential sums to evaluate is SUMPRODUCT(COMBIN(18,ROW($1:$18)) --
262,143.  If someone gave you a list of more than 20 numbers, that
would be a lot of sums to compute and compare (over 1 million).

You might want to place some reasonable constraints on the size of
your lists and on the number (or maximum number) of values that
comprise the sum.

HTH.

----- original posting -----

Does anyone have a list of numbers for which they need to find a set
that adds to a certain value? I am working on some code and would like
some real world examples to feed it.

For example, say I have the following list of numbers:

I want to find the combination of numbers that add to $76,395.94.

Does anyone have any lists they could post for me to test the code
with? Long or short lists will work, and real world examples are
preferable. Thanks!

Hi, thanks for the responses. What I meant to say is that I would like
a sample list of numbers and a target number to test with not
necessarily the number 76395.94. I went ahead and made a generator
which produced the list and target above, but I think it would be nice
to also have some other examples to test with.

 

[Bernie Deitrick]

With your list misssing the negative numbers, the code (original author is
Harlan Groves) below found this solution:

76,395.94 =
13852.8+11996.98+11508.32+11257.6+7047.06+5533.48+4305.22+4104.66+3145.03+2665.57+979.22

Follow the instructions for the references.

I have no idea how to fix the code to include negative numbers, which cause
it to fail - I have included a check to exclude negative numbers from the
list, so it will find a solution (if it exists) based on just the positive
numbers.

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 y > 0 Then
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
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 ----