Problem 3. (15 marks) Suppose you are a teller and the currency in your country
ID: 3705951 • Letter: P
Question
Problem 3. (15 marks) Suppose you are a teller and the currency in your country is arranged in coins of increasing C values (each coin has a value of a power of C for some integer C1), i.e., you have coins of le, Ce, C2e, .Ce up to some k 1. Your customer wants you to make change for Ne (N is a positive integer) using the minimum number of coins. Propose an efficient greedy algorithm in pseudocode which returns k +1 numbers no.n.n2..... nk such that (i) N - on,C and () the total number of coins used, o, is minimized. Prove that your algorithm is guaranteed to always return the optimal solution, that is, condition (ii is always satisfied. (Hint: Prove the two properties, subproblem optimality and substitution property, required for a greedy algorithm to work.)Explanation / Answer
The aim is to find the largestpossible denomination and subtract it from desired value.
After that, we have to find the largest possible denomination and subtract it from the remaining value.
repeat this process gain and again till you find the maximum possible denomination which is equal to the remaining value(the values of previous calculation).
The algorithm is greedy because at every step, we are finding optimum choice at each stage.
For example we have 1, 10, 100,1000 cents and we need a change for 120 cents.
By the algorithm we are discussing we will reduce 120 to 20 by deducting 100 cents.
Now,repeat this step tiil we can find another remainig value.now, the maximum possible denomination is 10.So 20 is reduced by 10 and repeat the same process again. Now,the maximum possible denomination is 10 which is equal to remaining value 10 and hence the algorithm is repeated.
The sequence of steps for the problem can be written as:
1. Initialise an array which should be empty - Change
2. Find the largest denomination X which isless than or equal to N
3. Reduce N by (N-X), add X into array Change
4. If N = 0, break
5. Else the repeat steps from 2 to 4
At the end of algorithm, the array Change will have denominations which adds up to N.
Proof:
If X=N then we have found the minimum number of coins which happens to be 1.
If X< N, then we look again for minimum valueof X' such that X' <= N' (N' = N-X).
Hence for every iteration,we are incrementing the value by 1,the minimum positive integer.
Therefore the algorithm will alway return the minimum number of coins.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.