Question for the math/computer programmer/Excel geniuses
 

Simple enough problem. I have a list of 25 numbers. Some, but not all of those numbers, when added up equal a known total. How do I figure out which of the numbers from the list equal my total.

Figured there would be a Java calculator for this, but in searching I don't find any on the web. I saw some advanced Excel/programming discussion, but wasn't able to understand how to translate 100 lines of code to Excel. Anyone know how to pull this off?

I'm not in your target group, but it sounds like an al Gebra problem to me...

I think that will be hard to do with plain Excel, without writing VBA code. I'd start by sorting the numbers in descending order and then solving manually, do it a couple times for different sets of 25 numbers, see if your process can be captured in spreadsheet functions.

but he wants an Al Gore rhythm here.

Well since you brought Al Gore into it:

I'd add up all the numbers, verify the result a couple of times to be absolutely sure it's correct, then report whatever you want anyway (even though it conflicts with the result) and then point to the original data set as "proof". Pretty simple.

So you are trying to find every possible permutation of any combo of these numbers which adds up to the magic number?

That's a Stu Pedasso comment.

Got the numbers and the known total to work for?

Since the numbers vary, x and y?

Yep, the tricky thing here is there could be multiple solutions. Solving this programatically would generally yield the first solution encountered.

I would probably create an array for each number and assign a number to that array for each iteration through the set. I would also store a sum for each iteration. This would allow me to keep track of what I've already added (to avoid duplication) and to see if there are multiple solutions.

The next trick is writing an algorithm that could successfully add each permutation of the numbers in the set. I'd have it start buy just "summing" each individual number, then every unique pair of numbers, then every unique set of three numbers, and so on up to the size of the set.

If you have access to a mainframe, I can whip up a recursive REXX exec that would spit out the combos in a jiffy...

When you say "adding together" do you mean only two numbers can be added together at a time, or can you have more? (ex: x+y only, or x+y, x+y+z, w+x+y+z...etc. ) If it is only two numbers at a time, you can probably write a macro for that using IF statements and < and > tests.

-Z-man.

Ok... here's the "word problem" version:

One of my clients put some business charges on her personal credit card. There were 25 charges in total (personal + business) on the credit card statement for the month. When the bill arrived, she paid a portion of the bill out of her personal checking account (unknown amount), and paid the business charges from the business checking account. So, I have the 25 charges on the credit card statement, and I have the amount paid from the business account.

She has the original statement somewhere, but moved a couple of months ago and it will take time to track down. I'm still surprised there wasn't a Java calculator posted for this.

"when added up equal a known total"

Exactly?
Equal to or greater than?
If so, then by no more than a certain #/%?
Seems it would be the exception rather than the rule that any pair of numbers would equal a known total, no?
Wish I was good at math. :(

So the number of possible sums is combin(25,1) + combin(25,2) + combin(25,3) + ... combin(25,25)?

That is only 33.5 million possible sums. you can do that in your head easy.

Yes... the exact total is the amount she paid from her business checking

Yes, but since we know the target sum, it seems like there is a minimum number of the set required to add up to at least that sum. So, if you add up the set from largest to smallest you can figure out that it will take at least that many members of the set to equal the total. Oh well... I know what i mean! :D

yea it's basically improbable that u'll find the matches. unless the set of 25numbers just happen to only coincidentally have one combination that match up to the total.

tell the client to get her receipts

This is the silly question that computers were made for. Google combination algorithms and wrtie a visual basic program to test all 33.55 millon of them.

The client can request the CC company to send a copy of that statement. It may be easier to then determine what was personal and what was business expense.

-Z-man.

I think that we've spent more time discussing this than it would have taken manually to figure this out...

Hmm - I've thought about it a little more, and have a question which may help clear up your dilema:

Do you know if one of her expenses was for a train ride? If so, was she travelling from Albuquerque, New Mexico to San Jose, California, at an average speed of 103 km/hr, while another tran was travelling from San Jose to Alburquerque at an average speed of 96km/hr? If she left Albuquerque at 3:06pm, and the train leaving from San Jose departed the trian depot at 1:23pm on the same day, at what time will the two trains meet? Bonus question: at what distance from San Jose will the trains meet?

Now, if one of her expenses was for an airline, then I have another question: was the plane on a conveyor belt when it took off?

One more question: did any of the transactions have anything to do with a Black Audi Wagon by any chance?

Yes, this will be on the final exam...

-Z-man.

Apologies for derailing (sic) this thread!

for the poorly educated among you (like Islet) my al Gebra post was pun on the fact that we inherited algebra from the Arabs

they developed it during the peak of their civilization, ~~ 1,000 AD

Post the 25 numbers and the amount paid and we'll figure it out.

I agree with doing some manual "prototypes" of this in Excel.

There is indeed a min. set that will satisfy your criteria & I don't think it will be in the millions. real issue is how many min. sets are there?

why not sort the 25 entries from largest to smallest; then copy the smallest 24 to a new worksheet; then copy 23... etc.

work back from there & rule out the small #'s - that should give at least one result

if not, keep track of it, and add back the biggest #, drop the 2nd biggest;

Lather/Rinse/Repeat

it's a weird Q. for me right now b/c I'm reading a book on Richard Feynmann and how when he was at Los Alamos, they set up "circles of girls on calculating machines" and ran things thru those circles until they got answers - and a bomb

I'd do a randomized approach.

1. Assign a random 0/1 value to each of the 25 Numbers
2. Add up the numbers with "1" value
3. If they add up to the goal value the you are set
4. If not cycle again

Leave the Excel woking all night and wake up to get the solution.

Post the numbers. I want to test my approach ;)

I am assuming this is for business deductions on a tax return...Here is the quick and dirty way I would do it:

1. Sort the receipts in column A
2. Add the receipts is column B
3. If yer lucky, one of the sums will be the exact number
4. If not lucky, select the receipts that get closest to the total
5. Call it a day, let the IRS figure the details out :D.

Good thing I am not a CPA :rolleyes:.

Amount paid from business checking = $1617.87
Charges:
486.87
32.48
247.84
9.64
27.19
30.00
79.36
28.17
119.53
26.79
530
141.65
11.4
40.83
53.15
36.93
11.40
84.25
44.39
58.25
328.53
175.82
182.44
332.67
3.87
-250.00 ... a $250 CREDIT from a return!

so far through trial and error I'm as close as 0.02

Here is your result:

486.87
32.48
247.84
9.64
27.19
30
79.36
28.17
119.53
26.79
530

That was easy my friend SmileWavy

I concur. At least that's a possible solution.

There might be other solutions, but since those were all grouped together on the top of the list, this has to be it.

Here's a link to an Excel template that does what you want. You will need the "Solver" add-in installed and enabled for it to work. I checked it out and it worked for me.
Excel Template - What Numbers In A Set Total A Target Value

Use the template I linked to and just let it run. It will run for about a minute.

486.87
27.19
79.36
28.17
530
11.4
40.83
11.4
44.39
175.82
182.44

There seems to be some funny accounting going on here. If you add up the first 11 items, they equal the exact amount paid on the business account. But if you look at my results, they also add up to the exact same amount. Do you want me to calculate the probability of that happening? Highly unlikely.

I think Aurel has it! She paid the balance toward the end of the month, but before the end of the statement period, so several of the later charges actually happened after my client made her payment.

I sent her a note asking which charges were tied to this payment. I'd expect she'll be able to confirm this eventually.

....use the Excel add-in programme called 'solver'....

easy peasy, lemon squeezy.......