Write an efficient algorithm for solving the make-change problem below, this tim

Question

Write an efficient algorithm for solving the make-change problem below, this time returning a fewest set of coins that makes change for the given amount, using the given set of denominations. What is the running time of your algorithm?

You have a 20 dollar bill and want to buy $17.52 worth of groceries. What is the fewest number of coins and bills the cashier can hand back to you?

More generally,

- the input consists of a value, which is the amount that needs to be made change for, and a list of denominations = [d0, d1, d2, ..., dn];

- the output is the minimum number of coins and/or bills needed to make change.

In the example above, value is 248 cents and denominations is the sequence 1, 5, 10, 25, 100, 500, 1000, 2000, 10000.

Explanation / Answer

Algorithm for make_change problem:

1. Sort all the denomination coins in increasing order of their value.
2. Initialize all the set of coins as empty. i.e.C = {}
3. While (total_amount) is not 0:
let Ck is largest coin such that x > Ck,
if there is no such coin
       return "no solution"
else:
        amount = amount - Ck
C = C U { Ck }

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

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