Problem 5. Define the problem of giving change as follows: Given a sorted array

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. :)

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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