A clerk in the U.S. store often encounters the problem of given change for a pur
ID: 3807764 • Letter: A
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.