Describe an efficient greedy algorithm for making changes for a specified value

Question

Describe an efficient greedy algorithm for making changes for a specified value using a minimum number of coins, assuming there are four denominations of coins (called quarters, dimes, nickels, and pennies) with values D_1 = 25, D_2 = 10, D_3 = 5, D_4 = 1, respectively. Argue why your algorithm is correct. If a new 20-cent coin (D_5 = 20) is created for the coin set, we can no longer use the greedy strategy to return change with the fewest number of coins. Devise a dynamic programming formulation that determines the fewest number of coins to return as change for coin denominations.

Explanation / Answer

Greedy Algorithm

Let Say we need minimum number of coins for Value = 40

1. Given denomination d = {25, 10, 5, 1} , We Sort the coins in decreasing Order
2. Divide the Total value by the first coin after sorting i.e 40/25 = 1 and remaining amount = 40%25 = 15
3. For remaining amount . Take the next items, Divide the remaining value by the second coin after sorting i.e 15/10 = 1 and remaining amount = 15%10 = 5
4. For remaining amount = 5. Take the next items, Divide the remaining value by the thord coin after sorting i.e 5/5 = 1 and remaining amount = 5%5 = 0

hence we get three number of coins = {25, 10, 5}

Lets say we added denomination of 20 and when we sort then we will get
{25, 20, 10, 5, 1}
Now for 40 , We will get {25, 10, 5 } still which is not correct because the minimim number of coins is 2
i.e {20, 20 }

So the GREEDY SOLUTION DOES NOT WORK HERE

Dynamic Programming

We can use DP to solve our problem , let the vaue of Coin be C

The minimum number of coins for a value C can be computed using below recursive formula.

Thanks, let me know if there is any doubts. Let me know if you need working code in any language. I will surely help.

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

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