Money Change Problem Consider the problem a cashier solves e

Money Change Problem:
Consider the problem a cashier solves every time she counts out some amount of currency. The cashier has at her disposal a collection of notes and coins of various denominations and is required to count out a specified sum using the smallest possible number of pieces.
Let us consider an example: For example, suppose we have ten coins: five pennies, two nickels, two dimes and quarter. i.e., to count out 32 cents, we start with a quarter, then add a nickel followed by two pennies. This is a greedy strategy because once a coin has been counted out it is never taken back. Furthermore, the solution obtained is the correct solution because it uses the fewest number of coins.
a. Will the above greedy strategy work for all cases using US coins (penny, nickel, dime and quarter)? Why/why not?
b. In the country called Bioinformatica, they use coins of denomination 1, 4, 5 and 20.
Will the same strategy work? Why/why not?

Solution

b)In the country called Bioinformatica, they use coins of denomination 1, 4, 5 and 20.
the same strategy doesnot work, For instance if we had to give out change for 12. As per greedy algorithm it would have picked 5 , 5 , 1 ,1 so in total 4 coins but the optimal solution would have been 4 , 4 ,4 ( 3 coins of 4value each)

a)

We apply the best solution for the current step
without regard for the optimal solution. This is usually easy to understand and
simple to implement. In the case of American currency, the greedy algorithm
provides the best solution because locally optimal solutions lead to globally
optimal solution as well.
Proof:
1. Let’s consider pennies and nickels. At most, I can use 4 pennies because any
number larger than 4 pennies would be replaced by at least 1 nickel. This
operation would reduce the total coin number by 4. In other words, when the
remainder is greater than 5 and I’m allowed to use only pennies and nickels, I
would use as many nickels as possible before considering pennies.
2. Let’s now consider pennies, nickels, and dimes. At most, I can use 1 nickel
because any number larger than 2 nickels would be replaced by at least 1 dime.
This operation would reduce the total coin number by 1. In other words,
when the remainder is greater than 10 and I’m allowed to use only penniesnickels, and dimes,
I would use as many dimes as possible before considering
nickels and pennies.
3. Now, let’s consider pennies, nickels, dimes, and quarters. At most, I can use 2
dimes because any number larger than 3 dimes would be replaced by 1 quarter
plus 1 nickel. This operation would reduce the total coin number by 1. In
other words, when the remainder is greater than 30, I would use as many
combinations of quarters and nickels as possible. Then, of course, the actual
amount of nickels used would fall into the second case. They would be
replaced by dimes if possible. So, the solution is to use as many quarters as
possible when the remainder is greater than 30.
4. For the gap between 25 and 30, based on the first two arguments, I would use
2 dimes, 1 nickel, and n 25 pennies. Obviously, I would use 1 quarter to
replace the 2 dimes and 1 nickel. This operation would reduce the total coin
number by 2.
Therefore, the greedy algorithm provides the optimal solution for this set of coin
denomination.