I was thinking about how I might go about solving a problem of, given an ATM that dispenses 50
's and 20
's, find all the combinations of notes dispensed that would be valid for a given amount.
Say, for 160
, that could be 8 20
's or 2 50
's and 3 20
's.
Now, I can do this in my head easily enough (for small numbers and only 2 variables), but I want to find out how to solve this properly.
As far as I can tell, this formula is Ax + By = C, where A = 20, B = 50, C = 160.
Because this is talking about real-world paper notes being dispensed, A and B both have to be integers >= 0.
I can plug this into Wolfram Alpha: http://www.wolframalpha.com/input/?i=%2850*x+%2B+20*y%29+%3D+160%3B+x+%3E%3D+0%3B+y+%3E%3D+0
So obviously a computer can determine the result.
But from my shaky recollection of high school mathematics, to solve something like this you need 2 equations to substitute in.
Or is my condition of "integers >= 0" another equation?
Also, there can be more than 1 answer (or 0 answers) for different values.
Is this done by brute-forcing numbers in a loop, or is there an equation you can use to solve this?
I had a look into matrixes, but most of it went over my head, and I couldn't figure out what I needed to actually insert into the matrix to find the result, or whether it was even applicable to my situation.