A clerk in the U.S. store often encounters the problem of given change for a pur

Question

A clerk in the U.S. store often encounters the problem of given change for a purchase because customers usually don't want to receive a lot of coins: 1c, 5c, 10c, 25c. What is an optimal solution to minimize the number of coins for a change? 1. Develop an iterative greedy algorithm to have the minimum number of coins for a change x cents. 2. The coins consist of U.S. coins which are available. The owed amount is 36 cents. What is an optimal solution? 3. Suppose that 12-cent coin with the U.S. coins is available. The owed amount is 16 cents. What is an optimal solution?

Explanation / Answer

Solution:

1)

2)

In 36 cents the optimal solution will be 25+10+1= 36 cents (3 coins)

3)

In this case 4 coins will be required that is 5+5+5+1= 16 (Four Coins),

But our greedy solution will give five coins as result and that will be 12+1+1+1+1= 16,

that is why we shift to dynamic programming in which the solution is optimal as will as time complexity is also less.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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