Phosphorus and Lime

My sister, an accountant, asked me if I could whip something up for her to help her crunch some numbers. Four months later...

What she wanted specifically was a program that could be given a set of numbers and a target amount and find the combination of numbers in the set that equals (or gets really close to) the target. I said surely there must be something in Excel that can do this for you. Apparently not. (Although I know now that I've finished someone will immediately point me to the Excel formula that does it.) So I came up with a ingenious brute force attack that could handle all of 16 or 17 numbers. Her sample set had 27.

It turns out this is a variation on a well-known and somewhat complex class of math problems: combinatorial optimization. A little further research led me to some strategies for pseudo-polynomial (as opposed to exponential) time algorithms (as an English major, I'm very proud to say that and say it every chance I get.) Eventually I put together something that seems to do the job.

Find the script here: klenwell.net

Here's the dataset my sister gave me:

373,643.70 27,232,550.00 7,820.80 113,089.00
10,250.00 13,919.75 30,763.08 83,165.38
46,572.53 7,500.00 2,000.00 263,912.00
1,056,367.56 275,892.42 3,000.00 60,486.01
248.24 165,513.08 4,708.25 200.00
1,427.28 300,000.00 400,000.00 178.77
151,802.82 210,250.00 266,700.00

Here's the target:

You can just copy and paste those in. I found the results surprising.