Algorithm Question

[Feldman]

I have a list of 1000 different numbers some positive and some negative. I need to find out what combination of numbers will produce a specific answer.

 

[kpark91]

So you want to add up all the elements in different subsets of your list to find the specific answer?

If so, you would have two types of algorithms which both require massive number of iterations.
O(2 ^ n)
and O(whatever, the other one is faster <lazy to type greek letters>)

Anyways, the algorithm would be setting it up as like a bit array.
So, if you were to have {1, 2, 3, 4}
1000 = 1
0100 = 2
0010 = 3
0001 = 4
1010 = 1 + 3 = 4

and so on...
Then you would have to check ur answer each time you get the answer and go onto next iteration.

 

[Feldman]

as an example here is a list of numers

<TABLE style="WIDTH: 48pt; BORDER-COLLAPSE: collapse" border=0 cellSpacing=0 cellPadding=0 width=64><COLGROUP><COL style="WIDTH: 48pt" width=64><TBODY><TR style="HEIGHT: 15pt" height=20><TD style="BORDER-BOTTOM: #f0f0f0; BORDER-LEFT: #f0f0f0; BACKGROUND-COLOR: transparent; WIDTH: 48pt; HEIGHT: 15pt; BORDER-TOP: #f0f0f0; BORDER-RIGHT: #f0f0f0" height=20 width=64 align=right>13190199</TD></TR><TR style="HEIGHT: 15pt" height=20><TD style="BORDER-BOTTOM: #f0f0f0; BORDER-LEFT: #f0f0f0; BACKGROUND-COLOR: transparent; HEIGHT: 15pt; BORDER-TOP: #f0f0f0; BORDER-RIGHT: #f0f0f0" height=20 align=right>1085133</TD></TR><TR style="HEIGHT: 15pt" height=20><TD style="BORDER-BOTTOM: #f0f0f0; BORDER-LEFT: #f0f0f0; BACKGROUND-COLOR: transparent; HEIGHT: 15pt; BORDER-TOP: #f0f0f0; BORDER-RIGHT: #f0f0f0" height=20 align=right>3646638</TD></TR><TR style="HEIGHT: 15pt" height=20><TD style="BORDER-BOTTOM: #f0f0f0; BORDER-LEFT: #f0f0f0; BACKGROUND-COLOR: transparent; HEIGHT: 15pt; BORDER-TOP: #f0f0f0; BORDER-RIGHT: #f0f0f0" height=20 align=right>-161017</TD></TR><TR style="HEIGHT: 15pt" height=20><TD style="BORDER-BOTTOM: #f0f0f0; BORDER-LEFT: #f0f0f0; BACKGROUND-COLOR: transparent; HEIGHT: 15pt; BORDER-TOP: #f0f0f0; BORDER-RIGHT: #f0f0f0" height=20 align=right>82314.76</TD></TR><TR style="HEIGHT: 15pt" height=20><TD style="BORDER-BOTTOM: #f0f0f0; BORDER-LEFT: #f0f0f0; BACKGROUND-COLOR: transparent; HEIGHT: 15pt; BORDER-TOP: #f0f0f0; BORDER-RIGHT: #f0f0f0" height=20 align=right>89539.07</TD></TR><TR style="HEIGHT: 15pt" height=20><TD style="BORDER-BOTTOM: #f0f0f0; BORDER-LEFT: #f0f0f0; BACKGROUND-COLOR: transparent; HEIGHT: 15pt; BORDER-TOP: #f0f0f0; BORDER-RIGHT: #f0f0f0" height=20 align=right>21677.42</TD></TR><TR style="HEIGHT: 15pt" height=20><TD style="BORDER-BOTTOM: #f0f0f0; BORDER-LEFT: #f0f0f0; BACKGROUND-COLOR: transparent; HEIGHT: 15pt; BORDER-TOP: #f0f0f0; BORDER-RIGHT: #f0f0f0" height=20 align=right>161849.3</TD></TR><TR style="HEIGHT: 15pt" height=20><TD style="BORDER-BOTTOM: #f0f0f0; BORDER-LEFT: #f0f0f0; BACKGROUND-COLOR: transparent; HEIGHT: 15pt; BORDER-TOP: #f0f0f0; BORDER-RIGHT: #f0f0f0" height=20 align=right>-9460892</TD></TR><TR style="HEIGHT: 15pt" height=20><TD style="BORDER-BOTTOM: #f0f0f0; BORDER-LEFT: #f0f0f0; BACKGROUND-COLOR: transparent; HEIGHT: 15pt; BORDER-TOP: #f0f0f0; BORDER-RIGHT: #f0f0f0" height=20 align=right>712.12</TD></TR><TR style="HEIGHT: 15pt" height=20><TD style="BORDER-BOTTOM: #f0f0f0; BORDER-LEFT: #f0f0f0; BACKGROUND-COLOR: transparent; HEIGHT: 15pt; BORDER-TOP: #f0f0f0; BORDER-RIGHT: #f0f0f0" height=20 align=right>1000</TD></TR><TR style="HEIGHT: 15pt" height=20><TD style="BORDER-BOTTOM: #f0f0f0; BORDER-LEFT: #f0f0f0; BACKGROUND-COLOR: transparent; HEIGHT: 15pt; BORDER-TOP: #f0f0f0; BORDER-RIGHT: #f0f0f0" height=20 align=right>15296.59</TD></TR><TR style="HEIGHT: 15pt" height=20><TD style="BORDER-BOTTOM: #f0f0f0; BORDER-LEFT: #f0f0f0; BACKGROUND-COLOR: transparent; HEIGHT: 15pt; BORDER-TOP: #f0f0f0; BORDER-RIGHT: #f0f0f0" height=20 align=right>2767.65</TD></TR><TR style="HEIGHT: 15pt" height=20><TD style="BORDER-BOTTOM: #f0f0f0; BORDER-LEFT: #f0f0f0; BACKGROUND-COLOR: transparent; HEIGHT: 15pt; BORDER-TOP: #f0f0f0; BORDER-RIGHT: #f0f0f0" height=20 align=right>1560699</TD></TR><TR style="HEIGHT: 15pt" height=20><TD style="BORDER-BOTTOM: #f0f0f0; BORDER-LEFT: #f0f0f0; BACKGROUND-COLOR: transparent; HEIGHT: 15pt; BORDER-TOP: #f0f0f0; BORDER-RIGHT: #f0f0f0" height=20 align=right>-2000</TD></TR><TR style="HEIGHT: 15pt" height=20><TD style="BORDER-BOTTOM: #f0f0f0; BORDER-LEFT: #f0f0f0; BACKGROUND-COLOR: transparent; HEIGHT: 15pt; BORDER-TOP: #f0f0f0; BORDER-RIGHT: #f0f0f0" height=20 align=right>1986648</TD></TR><TR style="HEIGHT: 15pt" height=20><TD style="BORDER-BOTTOM: #f0f0f0; BORDER-LEFT: #f0f0f0; BACKGROUND-COLOR: transparent; HEIGHT: 15pt; BORDER-TOP: #f0f0f0; BORDER-RIGHT: #f0f0f0" height=20 align=right>3524935</TD></TR><TR style="HEIGHT: 15pt" height=20><TD style="BORDER-BOTTOM: #f0f0f0; BORDER-LEFT: #f0f0f0; BACKGROUND-COLOR: transparent; HEIGHT: 15pt; BORDER-TOP: #f0f0f0; BORDER-RIGHT: #f0f0f0" height=20 align=right>513557.7</TD></TR><TR style="HEIGHT: 15pt" height=20><TD style="BORDER-BOTTOM: #f0f0f0; BORDER-LEFT: #f0f0f0; BACKGROUND-COLOR: transparent; HEIGHT: 15pt; BORDER-TOP: #f0f0f0; BORDER-RIGHT: #f0f0f0" height=20 align=right>1321762</TD></TR><TR style="HEIGHT: 15pt" height=20><TD style="BORDER-BOTTOM: #f0f0f0; BORDER-LEFT: #f0f0f0; BACKGROUND-COLOR: transparent; HEIGHT: 15pt; BORDER-TOP: #f0f0f0; BORDER-RIGHT: #f0f0f0" height=20 align=right>-155646</TD></TR><TR style="HEIGHT: 15pt" height=20><TD style="BORDER-BOTTOM: #f0f0f0; BORDER-LEFT: #f0f0f0; BACKGROUND-COLOR: transparent; HEIGHT: 15pt; BORDER-TOP: #f0f0f0; BORDER-RIGHT: #f0f0f0" height=20 align=right>100</TD></TR><TR style="HEIGHT: 15pt" height=20><TD style="BORDER-BOTTOM: #f0f0f0; BORDER-LEFT: #f0f0f0; BACKGROUND-COLOR: transparent; HEIGHT: 15pt; BORDER-TOP: #f0f0f0; BORDER-RIGHT: #f0f0f0" height=20 align=right>348.06</TD></TR><TR style="HEIGHT: 15pt" height=20><TD style="BORDER-BOTTOM: #f0f0f0; BORDER-LEFT: #f0f0f0; BACKGROUND-COLOR: transparent; HEIGHT: 15pt; BORDER-TOP: #f0f0f0; BORDER-RIGHT: #f0f0f0" height=20 align=right>18107.5</TD></TR><TR style="HEIGHT: 15pt" height=20><TD style="BORDER-BOTTOM: #f0f0f0; BORDER-LEFT: #f0f0f0; BACKGROUND-COLOR: transparent; HEIGHT: 15pt; BORDER-TOP: #f0f0f0; BORDER-RIGHT: #f0f0f0" height=20 align=right>42506.04</TD></TR><TR style="HEIGHT: 15pt" height=20><TD style="BORDER-BOTTOM: #f0f0f0; BORDER-LEFT: #f0f0f0; BACKGROUND-COLOR: transparent; HEIGHT: 15pt; BORDER-TOP: #f0f0f0; BORDER-RIGHT: #f0f0f0" height=20 align=right>211.99</TD></TR><TR style="HEIGHT: 15pt" height=20><TD style="BORDER-BOTTOM: #f0f0f0; BORDER-LEFT: #f0f0f0; BACKGROUND-COLOR: transparent; HEIGHT: 15pt; BORDER-TOP: #f0f0f0; BORDER-RIGHT: #f0f0f0" height=20 align=right>-2873450</TD></TR><TR style="HEIGHT: 15pt" height=20><TD style="BORDER-BOTTOM: #f0f0f0; BORDER-LEFT: #f0f0f0; BACKGROUND-COLOR: transparent; HEIGHT: 15pt; BORDER-TOP: #f0f0f0; BORDER-RIGHT: #f0f0f0" height=20 align=right>-125780</TD></TR><TR style="HEIGHT: 15pt" height=20><TD style="BORDER-BOTTOM: #f0f0f0; BORDER-LEFT: #f0f0f0; BACKGROUND-COLOR: transparent; HEIGHT: 15pt; BORDER-TOP: #f0f0f0; BORDER-RIGHT: #f0f0f0" height=20 align=right>2912.66</TD></TR><TR style="HEIGHT: 15pt" height=20><TD style="BORDER-BOTTOM: #f0f0f0; BORDER-LEFT: #f0f0f0; BACKGROUND-COLOR: transparent; HEIGHT: 15pt; BORDER-TOP: #f0f0f0; BORDER-RIGHT: #f0f0f0" height=20 align=right>6070.55</TD></TR><TR style="HEIGHT: 15pt" height=20><TD style="BORDER-BOTTOM: #f0f0f0; BORDER-LEFT: #f0f0f0; BACKGROUND-COLOR: transparent; HEIGHT: 15pt; BORDER-TOP: #f0f0f0; BORDER-RIGHT: #f0f0f0" height=20 align=right>20413.13</TD></TR><TR style="HEIGHT: 15pt" height=20><TD style="BORDER-BOTTOM: #f0f0f0; BORDER-LEFT: #f0f0f0; BACKGROUND-COLOR: transparent; HEIGHT: 15pt; BORDER-TOP: #f0f0f0; BORDER-RIGHT: #f0f0f0" height=20 align=right>1557151</TD></TR></TBODY></TABLE>

I know the answer is 16455.56
Is there a way for excel to find the numbers that when combined will equal this number

 

[kpark91]

Yes there is. And it's through using VBA.
Try checking this website out:
http://stackoverflow.com/questions/403865/algorithm-to-sum-up-a-list-of-numbers-for-all-combinations

Altho, it's not VBA there's a solution to this problem. But once again, I will say that with 1000 different numbers to check, I doubt you will be able to run it under 12 hours.

 

[Ruddles]

I have a list of 1000 different numbers some positive and some negative. I need to find out what combination of numbers will produce a specific answer.

What's the most numbers that can be in a combination? Could it be every number, for example? Or is there a maximum number of numbers in each combination?

 

[Ruddles]

Never mind the answer to that - here's some code which should do the job. Place your numbers in column A starting from A2. Leave column B blank as that will contain any results. (Comment out the code in blue if you don't want this. Comment out the code in red if you don't want the message boxes.) Place your target value in vTargetValue.

[FONT=Fixedsys]Option Explicit[/FONT]
[FONT=Fixedsys][/FONT] 
[FONT=Fixedsys]Sub CombineAndCheckTotal()[/FONT]
[FONT=Fixedsys][/FONT] 
[FONT=Fixedsys]  Const vTargetValue As Variant = 16455.56
  
  Dim ws As Worksheet
  Dim vArray As Variant
  Dim sMask As String
  Dim iLastRow As Long
  Dim iRow As Long
  Dim vTotal As Variant
  Dim iInd As Long
  Dim sMessage As String
  Dim iOutRow As Long
  Dim dStart As Date
  
  Application.Cursor = xlWait
  
  dStart = Now()
  Set ws = ThisWorkbook.Sheets(1)
  iLastRow = ws.Cells(ws.Rows.Count, "A").End(xlUp).Row
  vArray = Application.Transpose(ws.Range("A2:A" & iLastRow))
  sMask = String(UBound(vArray), "0")
  iOutRow = 1
  
  Do Until sMask = String(UBound(vArray), "1")
    Increment sMask
    vTotal = 0
    For iInd = 1 To UBound(vArray)
      If Mid(sMask, iInd, 1) = "1" Then vTotal = vTotal + vArray(iInd)
    Next iInd
    vTotal = Round(vTotal, 2)
    If vTotal = vTargetValue Then
      sMessage = ""
      For iInd = 1 To UBound(vArray)
        If Mid(sMask, iInd, 1) = "1" Then sMessage = sMessage & ", " & vArray(iInd)
      Next iInd
[COLOR=green]      ' option #1 - display combination on worksheet
[/COLOR][COLOR=blue]      If iOutRow = 1 Then ws.Columns("B").ClearContents
      iOutRow = iOutRow + 1
      ws.Cells(iOutRow, "B") = Mid(sMessage, 2)
[/COLOR][COLOR=green]      ' option #2 - display combination in message box
[/COLOR][COLOR=red]      MsgBox "Combination found:-" & Space(10) & vbCrLf & Replace(sMessage, ",", vbCrLf & Space(5)), _
             vbOKOnly + vbInformation
[/COLOR]    End If
    DoEvents
  Loop
  
  Application.Cursor = xlDefault
  
  MsgBox "Finished:-" & vbCrLf & vbCrLf _
       & Space(5) & CStr(iLastRow - 1) & " numbers in list" _
       & Space(10) & vbCrLf & vbCrLf _
       & Space(5) & Format(2 ^ (iLastRow - 1) - 1, "#,###") & " combinations checked" _
       & Space(10) & vbCrLf & vbCrLf _
       & Space(5) & "Run time: " & Format(Now() - dStart, "hh:nn:ss") & Space(10), _
       vbOKOnly + vbInformation
       
End Sub[/FONT]
[FONT=Fixedsys][/FONT] 
[FONT=Fixedsys]Function Increment(ByRef aMask As String)[/FONT]
[FONT=Fixedsys][/FONT] 
[FONT=Fixedsys]  Dim iPtr As Integer
  
  For iPtr = 1 To Len(aMask)
    If Mid(aMask, iPtr, 1) = "0" Then
      Mid(aMask, iPtr, 1) = "1"
      Exit Function
    Else
      Mid(aMask, iPtr, 1) = "0"
    End If
  Next iPtr[/FONT]
[FONT=Fixedsys][/FONT] 
[FONT=Fixedsys]End Function
[/FONT]

The result is: 18107.5, -2000, 348.06.

Run time was not good: for 18 numbers it was 10 seconds, for 19 numbers it was 20 seconds, and for 20 numbers it was 40 seconds. I haven't worked out what the time for 1000 numbers would be but I'm sure you can do the maths. Test the code on a small set of simple numbers before tying your machine up overnight - or longer!

And if anyone can come up with a quicker algorithm, I'd be very interested in seeing it.

 

[Feldman]

Thanks for all the help, I am running it now. I will let you know the results when it is finished.

 

[Ruddles]

Did you try it on a small set of simple numbers first?

 

[Feldman]

It works, but I am now trying to find ways to make it faster. For now I am looking at ways to reduce the original list. Thanks for all your help.

 

[mikerickson]

Have you googled "greedy algorithm"?
Are you aware that there may be more than one solution?