Write an efficient algorithm for solving the makechange prob

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.

Solution

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 C_k is largest coin such that x > C_k,
if there is no such coin
       return \"no solution\"
else:
        amount = amount - Ck
C = C U { C_k }