16-1 Coin changing Consider the problem of making change for n cents using the f
ID: 3729847 • Letter: 1
Question
16-1 Coin changing Consider the problem of making change for n cents using the fewest number of coins. Assume that each coin's value is an integer a. Describe a greedy algorithm to make change g of quarters, dimes, nickels, and pennies. Prove that your algorithm yields an optimal solution. Problems for Chapter 16 447 b. Suppose that the available coins are in the denominations that are powers of c, i.e., the denominations are c.c1....ck for some integers c> 1 and k Show that the greedy algorithm always yields an optimal solution. c. Give a set of coin denominations for which the greedy algorithm does not yield an optimal solution. Your set should include a penny so that there is a solution or every value of n. d. Give an O(nk)-time algorithm that makes change for any set of k different coin denominations, assuming that one of the coins is a penny.Explanation / Answer
a) A greedy solution for the problem is to take out the count of maximum no. of quarters that divides the total integer value, then count of maximum no. of dimes that divides the total integer value, then similarly for nickels and for pennies. This leads to optimal solution because we take out a coin of maximum denominations mj (assume) then a we have to find the optimal solution for X-mj . For this maximum denomination, we choose the maximum coin possible that can be seen by greedy solution.
b)Since the coins are divisible by each other i.e. c0, c1, c2, ..., ck so we can prove that optimal solution will lead to greedy solution by we have an amount of money X, with cj X< cj+1. Whatever the optimal coin representation of X is, it can be proved to be minimal thus proving the solution to be optimal.
c) For X=10 and demonimation = { 1, 2, 3, 5, 6} then according to greedy solution is {6, 3, 1} count = 3 while the solution should be {5, 5} so here a greedy solution does not yield an solution.
d) If N == 0, then 0 coins required.
If N>0 minCoins (coins[1,2,...k],N) = min (1+ minCoins(N-coins[i])
where i varies from 1,2,..k
and coins[i]<=N
Therefore, O(nK) .as can be seen from the algorithm above.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.