OT: Elementary Math Problem

[Karim]

The concept is simple. Payment is made that exceeds the bill. Determine the least amount of coins and bills required to make change.

Solving the problem isn't what I'm after as a recursive solution works. What I'm wondering is if there is a general formula that works regardless of the amount paid or the cost of the bill? Could it be done without introducing a new variable for each type of coin and bill?

[Chubby]

umm my head :)

As a cashier for 2 years in HS, I got to be pretty good at making change...

[ntndeacon]

Sounds like an optimmization problem to me. not sure how simple a general fomula would have to be.

[Draft Dodger]

there's a flaw in my math somewhere - but the below excel formula works for many amounts

anyways, replace 'a1' with your amount and this will calculate the number of coins you need in most cases. not sure why some numbers don't work right...

C=INT(A1/0.25)+INT((A1-((INT(A1/0.25))*0.25))/0.1)+(INT((A1-((INT(A1/0.25))*0.25)-((INT((A1-((INT(A1/0.25))*0.25))/0.1))*0.1))/0.05))+(INT((A1-((INT(A1/0.25))*0.25)-((INT((A1-((INT(A1/0.25))*0.25))/0.1))*0.1)-((INT((A1-((INT(A1/0.25))*0.25)-((INT((A1-((INT(A1/0.25))*0.25))/0.1))*0.1))/0.05))*0.05))/0.01))

[Sun Tzu]

C=INT(A1/0.25)+INT((A1-((INT(A1/0.25))*0.25))/0.1)+(INT((A1-((INT(A1/0.25))*0.25)-((INT((A1-((INT(A1/0.25))*0.25))/0.1))*0.1))/0.05))+(INT((A1-((INT(A1/0.25))*0.25)-((INT((A1-((INT(A1/0.25))*0.25))/0.1))*0.1)-((INT((A1-((INT(A1/0.25))*0.25)-((INT((A1-((INT(A1/0.25))*0.25))/0.1))*0.1))/0.05))*0.05))/0.01))

If any of you out there have been wondering if Draft Dodger is an Alien from outer space, I think you have your answer right there.

[sterlingice]

If any of you out there have been wondering if Draft Dodger is an Alien from outer space, I think you have your answer right there.
Looks a lot like the stuff I was messing with last night (lots of nested IFs). Then again, this just required a case statement in Excel to look prettier.
=IF($O2=17,D2*1.76,IF($O2=18,D2*1.53,IF($O2=19,D2*1.33,IF($O2=20,D2*1.21,IF($O2=21,D2*1.11,IF($O2=22,D2*1.1,IF($O2=23,D2*1.05,D2)))))))

SI

[Karim]

Cool. Thanks, guys!