Challenge. 1

[fredericofonseca]

Hi all,

As part of my work I have sometimes to reconcile lists of amounts in such a way that any combination of them matches a particular value or list of values.

sample.

a=-100
b=-20
c=20
d=250
e=350
f=700
g=100

I want to find the possible combinations whereby adding 1 or more values match 600.

on the above list the following is possible
a+b+c+d+e+g = 600
a+d+e+g=600
d+e=600

Using Excel up to 2003, I was limited to a maximum of 11+1 values using a list of 1, 0, -1 multiplication/sums.
With 2007 limit a lot higher, but quite a bit of memory required.

I've looked into solver and similar trying to find a way to do the above, but could not managed to get a way to do it.

Anyone has a idea of how this type of calculation could be done with excel 2003 or 2000 (sometimes only available), for a list of up to 2000 values?



Regards

Frederico Fonseca
SysSoft Integrated Ltd

http://www.syssoft-int.com

FAQ219-2884
FAQ181-2886

 

[macropod]

Hi,

The following macro (which I found somewhere a long time ago ... ) checks all cell pairs and triplets in the selected rows and reports any that add up to the value stored in the nominated target cell:

Sub FindSubSets()
Application.ScreenUpdating = False
Dim a As Long
Dim b As Long
Dim c As Long
Dim d As Long
Dim Target As String
Dim Output As String
Dim x As Long
Dim y As Long
Dim z As Long
If Selection.Rows.Count = 1 Or Selection.Columns.Count <> 1 Then
  MsgBox "Please select more than one row in a single column"
  Exit Sub
End If
a = ActiveCell.Row
b = ActiveCell.Column
c = Selection.Rows.Count + ActiveCell.Row - 1
d = 0
Target = InputBox("What is the address of the cell" & vbCrLf & "you want the numbers to add up to?")
Output = InputBox("What is the address of the first cell" & vbCrLf & "you want to output the results in?")
On Error GoTo Abort
Range(Output).Offset(d, 0) = ""
For x = a To c
  For y = x + 1 To c
  If Cells(x, b) + Cells(y, b) = Range(Target).Value Then
    Range(Output).Offset(d, 0) = Addr(x, b) + "+" + Addr(y, b)
    d = d + 1
  Else
    For z = y + 1 To c
    If Cells(x, b) + Cells(y, b) + Cells(z, b) = Range(Target).Value Then
      Range(Output).Offset(d, 0) = Addr(x, b) + "+" + Addr(y, b) + "+" + Addr(z, b)
      d = d + 1
    End If
    Next z
  End If
  Next y
Next x
Range(Output).Offset(d, 0) = ""
Abort:
Application.ScreenUpdating = False
End Sub
Private Function Addr(ByVal n As Integer, ByVal m As Integer) As String
  Addr = Cells(n, m).Address(False, False)
End Function

If you need quartets etc, the above code should serve as a good starting point.

Cheers

[MS MVP - Word]

 

[fredericofonseca]

macropod,

I already have a VBA solution, but due to the sometimes quite big list required (up to 2000 values), it ends up being a bit slow to do all permutations of them.

I was more trying to see if any of the analysis tools would have any function that could solve it.

Sometimes from the full list I am given, 20 or 30 of the values make up to the value we are searching for. Other times its only 4 or 5, but given that the number will be both positive and negative numbers, not really easy to figure out manually.

Regards

Frederico Fonseca
SysSoft Integrated Ltd

http://www.syssoft-int.com

FAQ219-2884
FAQ181-2886

 

[lionelhill]

It will be a bit slow whatever you use to do it.

In the worst case scenario, 2^2000 combinations is a phenomenally large number.

In the still-pretty-awful case that you describe of 20-30 values, it still needs to look at 2000*1999*1998...*1980, which is a very great deal of combinations.

And as you've noted, because you have negative numbers, it cannot reject combinations as soon as they exceed the target value.

This is not a problem where simple combination-testing scales well.