Need Combination of dollar amounts that match entered dollar amount

[brandonmcg]

If I enter a dollar amount (will use $1,513.30 for this example) I need an x or other identifier to show me which amounts combined match that dollar amount. What would a formula look like and maybe even a MACO?

Amount	Looking For Match To This Amount
	$1,513.30
-$36.15
$0.01
$1.06
$11.22	x
$1.35
$1.57
$5.66	x
$4.12
$7.85
$383.55	x
$1,112.87	x
$1,380.97

<colgroup><col width="80" style="width: 60pt; mso-width-source: userset; mso-width-alt: 2925;"> <col width="223" style="width: 167pt; mso-width-source: userset; mso-width-alt: 8155;"> <tbody> </tbody>

 

[Eric W]

This is actually a pretty HARD task! If you have more than a few amounts, you'll end up with many possibilities. In your example, there only seems to be one. This was the subject of a MrExcel Challenge about 17 years ago. The winner wrote a macro to solve it. Quite impressive. Here's the link:

https://www.mrexcel.com/challenges/accounts-receivable-challenge/

To try it, open a new workbook. Press Alt-F11 to open the VBA editor. Press Alt-IM. Copy the code from the box that says: [FONT=&quot]IOANNIS's winning macro, and paste it into the window that opened. Press Alt-IM again. Paste the code from the "Module 2" box into that window. Go back to your Excel sheet and paste your values into B1:B12. Put the number of values in F1, and the target amount into F2. Your sheet should look like:

[/FONT]

Book1
	A	B	C	D	E	F
1		($36.15)				12
2		$0.01				1,513.30
3		$1.06
4		$11.22
5		$1.35
6		$1.57
7		$5.66
8		$4.12
9		$7.85
10		$383.55
11		$1,112.87
12		$1,380.97
Sheet1

Press Alt-F8, and choose the Challenge macro and click Run. Your sheet should now look like:

Book1
	A	B	C	D	E	F	G	H
1		($36.15)				12		7 9 10 11
2		$0.01				1,513.30
3		$1.06				11
4		$1.35				12
5		$1.57
6		$4.12
7		$5.66				0
8		$7.85
9		$11.22
10		$383.55			12
11		$1,112.87
12		$1,380.97
13
14						5:14:00 PM
15						5:14:00 PM
16
17
18						0
Sheet1

F14 has the start time, F15 has the end time. H1 has the solution. Take the numbers from rows 7, 9, 10, and 11, and they add up to 1,513.30. If there are multiple answers, you'll get those combinations going down the H column.

Good luck!

 

[lrobbo314]

Give this a shot. The code assumes that your amounts are in A3:A14, and the amount you are looking for is in B1. I just copied and pasted from your OP and that's how it came out. If that's not where your data is the code will need to be adjusted. When I ran the code, it output the results to D1 and says 'Rows: 6,9,12,13', which is correct!

Public Trgt As Double

Sub FINDINVOICES()
Dim AR() As Variant: AR = Range("A3:A" & Range("A" & Rows.Count).End(xlUp).Row).Value
Dim i As Integer

Trgt = Range("B2").Value

For i = 2 To UBound(AR)
    Combo AR, i, 1, 0, 0, ""
Next i

End Sub

Sub Combo(AR As Variant, grp As Integer, id As Integer, dpth As Integer, Total As Double, ro As String)
Dim acc As Double
Dim buf As String

For i = id To UBound(AR)
    acc = Total + AR(i, 1)
    buf = ro & i + 2 & ","
    If dpth + 1 = grp Then
        If acc = Trgt Then
            Range("D1").Value = "Rows: " & Left(buf, Len(buf) - 1)
            End
        End If
    Else
        Combo AR, grp, i + 1, dpth + 1, acc, buf
    End If
Next i

End Sub

 

[Eric W]

Give this a shot. The code assumes that your amounts are in A3:A14, and the amount you are looking for is in B1. I just copied and pasted from your OP and that's how it came out. If that's not where your data is the code will need to be adjusted. When I ran the code, it output the results to D1 and says 'Rows: 6,9,12,13', which is correct!

Public Trgt As Double

Sub FINDINVOICES()
Dim AR() As Variant: AR = Range("A3:A" & Range("A" & Rows.Count).End(xlUp).Row).Value
Dim i As Integer

Trgt = Range("[COLOR=#ff0000]B2[/COLOR]").Value

For i = 2 To UBound(AR)
    Combo AR, i, 1, 0, 0, ""
Next i

End Sub

Sub Combo(AR As Variant, grp As Integer, id As Integer, dpth As Integer, Total As Double, ro As String)
Dim acc As Double
Dim buf As String

For i = id To UBound(AR)
    acc = Total + AR(i, 1)
    buf = ro & i + 2 & ","
    If dpth + 1 = grp Then
        If acc = Trgt Then
            Range("D1").Value = "Rows: " & Left(buf, Len(buf) - 1)
            End
        End If
    Else
        Combo AR, grp, i + 1, dpth + 1, acc, buf
    End If
Next i

End Sub

I think you meant B2.

I thought about writing a recursive routine to figure this out, so when I saw you did, I played around with it a little. It works, in this limited example, but with a larger number of amounts, it takes too long. I ran it on the sample from the challenge, and it ran for hours without finishing. Yours also quits after it finds one solution, where there could be many. I'm sure it would be possible to improve this, say by adding a check that if the current total exceeds the target, then don't try adding any more numbers. But even with that, I don't think it would help a lot. You'd need a more sophisticated algorithm, which is what I like about the solution from the challenge.

 

[lrobbo314]

The OP didn't deem to be looking for multiple answers, but that's easy enough to add. I ran the challenge too and same thing, ran for hours without finishing. Not sure how they validated winning the challenge, lol.

I don't know how you would solve this without checking all combinations. Just looking at the challenge, I didn't really understand what was going on. Didn't really feel like stepping through those tons of lines of code to see what was going on. If it is more optimal, it still ran really slowly.

Oddly enough when looking at the task manager, the recursion seemed to spread across the logical processors of the CPU whereas the challenge pinned just 1 of the 4.

 

[Eric W]

I manually checked 3 or 4 of the results that came from the challenge macro, and they added up. I had no intention of doing all of them! But short of testing every combination, I don't know how to say that it didn't miss a combination or two. I've done a little digging into the theory, and this is an NP-Complete problem. (NP = Non-polynomial). Which, as you suspect, means that you really do have to check all 2^n combinations. However, that's the general case. It's possible that some sub-case of the problem is more amenable to calculation. Maybe that all the numbers are positive? And sorted? I don't know either. I've poked around a bit in that code, and I understood pieces, but the whole of it still eludes me.

You make an interesting point about the recursion spreading the processing to multiple processors. Parallel processing seems to be the wave of the future for "big" problems. Since every time you call your recursive routine, it creates a new mini-environment, maybe that makes it easier to spread around. I'm guessing.

 

[lrobbo314]

I did see that his code sorted the values at the beginning. That must have something to do with cutting down the calculations.

For bigger data sets that need every combination, I've found that Python is easier to code and runs faster. But that challenge has some odd quadrillion combinations. No matter what, that's going to take forever.

I've burned too many calories thinking about this already, lol. Let's just keep track of our transactions so we don't need to put them back together in this bass-akwards way.