Problem 5. Define the problem of giving change as follows: Given a sorted array
ID: 3704738 • Letter: P
Question
Problem 5. Define the problem of giving change as follows: Given a sorted array A of n distinct, positive integers with A[1-1 and a positive integer u, return an array B of length n such that i A[i] * Bli] = u and BIn] is minimized. A represents the different coins, v is the amount of money needing to be returned, B tells us how many of each kind of coin to use, and the restrictions on B ensure that the correct amount is returned and the number of coins used is minimized. For U.S. currency, for instance, A 1,5,10,25,50, 100]. Then for v 289, B [4,0, 1,1, 1,2]. Note that A[1]1 s included to ensure that there is always a solution Describe a greedy algorithm to solve this problem. Analyze its runtime. The greedy approach does not guarantee an optimal solution for all A. Give an example where the greedy algorithm would return a solution that uses at least 5 more coins than necessary.Explanation / Answer
Solution:
The algorithm is given below:
Algorithm:
Correctness:
The above greedy algorithm is simply finding the biggest denomination and then goes on for the smallest one's one by one, it won't give optimal result since it a greedy approach.
Running time:
The running time of this algorithm is O(n) since only one loop is there which is running for all the currency denominations.
Failure:
Currency = {25, 16, 1}
Total Value = 32
Greedy solution:
Number of coins [1,0,7] for currency [25,16,1] respectively
Optimal Solution:
Number of coins [0,2,0] for currency [25,16,1] respectively
Difference in total coins 8-2=6 and uses 6 coins more than necessary
I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)