Money Change Problem: Consider the problem a cashier solves every time she count

Question

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 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?

Explanation / Answer

Inputs: number of units to make change for n
Outputs: number of half dollars, quarter, dimes, nickels, and pennies to use (c50; c25; c10; c5; c1).
MAKECHANGE(n)
(a) c50 = n div 50
(b) leftover = n mod 50
(c) c25 = n div 25
(d) leftover = n mod 25
(e) c10 = n div 10
(f) leftover = n mod 10
(g) c5 = n div 5
(h) leftover = n mod 5
(i) c1 = n div 1
(j) leftover = n mod 1
(k) return (c50; c25; c10; c5; c1)
Because the algorithm always performs 10 calculations, it’s worst-case running time is (1)

Related Questions

Navigate

• Browse (All)
• Browse M
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.