I've read so many about the Coin Change problem, debates about wheather it is solvable using Greedy, Dynamic Programming and so on.
Nevertheless I cannot find an application of this problem.
What are applications of Coin Change problem?
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
This is going to sound very silly but, I once had to implement the coin change solution for the purpose of... distributing change!
The application was a soda pop vending machine that could accept bills and coins and dispense coins.
The spec required the use of a least coin pay, plus an alternative algorithm should one of the coin tubes be empty and thus unable to dispense coins of that denomination.
The classic example was buying a 60 cent soda pop with a dollar (I know, pop was cheap back then ;-). This leaves 40 cents change, or in the US, 1 quarter, 1 dime, and 1 nickel for least coin pay. If the nickel tube were empty though, the machine would dispense 4 dimes.
I know to is not quite the lofty heights of academia, but it was an actual application of the problem's solution. On a further note, more modern coin changer mechanisms implement their own coin management so for those more capable peripherals, we would just let the coin mech figure out if change could be made.
If not, the customer would get the dreaded NO CHANGE error message and the money would be returned.
$\begingroup$
$\endgroup$
Coin change problem is actually a very good example to illustrate the difference between greedy strategy and dynamic programming. For example, this problem with certain inputs can be solved using greedy algorithm and with certain inputs cannot be solved (optimally) using the greedy algorithm. However, dynamic programming version can solve all cases.
A simple example can be as follows. Let's say that you have N tons stuff, to be delivered from one place to another place. You can use airplane (capacity 100 tons), big truck (capacity 15 tons), medium truck (capacity 10 tons), etc. How do you manage to send your N tons of stuff with the minimum number of facilities? There are an infinite number of applications that you can find.
