Can someone help me with these Greedy Algorithm question? Please walk me through

Question

Can someone help me with these Greedy Algorithm question? Please walk me through your steps, not just give me the answer, I want to be able to replicate and learn what you are doing.

Given that you have coins in 1 cent, 5 cent, 10 cent, 25 cent and 1 dollar (100 cents) form. Develop a greedy algorithm pay the customer with the smallest number of coins. For example, 28 cents can be paid by using one 25 cent coin, 3 one cent coins. You only have to describe the algorithm and write the pseudocode. No code is necessary. (20) Prove that your algorithm does indeed give the correct answer (20) For some coin denominations the greedy algorithm will not work. One example is if the denominations are (1,3 and4) cents. Give two other sets of denominations where the greedy algorithm will not work, and give in stances where they fail. HINT: Try to pick denominations that are not multiples of each other (5 2 10)

Explanation / Answer

The objective is to pay the customer with the minimum numbers of coins. The denominations are 1,5,10,25 and 100 cents.
Let's say we have to pay X cents to the customer, So, we'll first check that is X is greater than the highest denomination 100, if yes, then get the modulus(remainder) of X and store dividend to count. Say, it is Y, now check if Y is greater than second highest 50. If yes, then go on and get the modulus and add dividend to count. At last, when the modulus is smaller than 5, then that's the number of coins of denomination 1 and add it to cont. Count is the total numbers of minimum coins requried to pay X.

otherwise, if x is smaller than 100, then go to second highest 50 , and repeat the process, and thus you will get the minimum number of coins.

Pseudocode:

min_coins(denominations_set, X){       //function min_coins takes set and an integer as an argument
   i = length(denominations_set)       //set i to index of denomination with max value
   while(denominations_set(i) > X){   //find max value of coin in denominations set which is less than X.
       i=i-1;
   }
   tcoin = denominations_set(i)       //set tcoin value to max coin value which is less than X.
   count=0                              
   while(tcoin<X){
       count += X/tcoin
       remain = X % tcoin
       X = remain
       i=i-1
       while(denominations_set(i) > X){
           i=i-1
       }
       tcoin = denominations_set(i-1)
   }

   return count
}

Proof of Correctness:

two other sets where this algorithm will not works:
   1) denominations set = {1, 7, 9} cents
   to pay 14 cents
   our algorithm will retrun 1 coin of 9 and 5 coins of 1, total of 6 coins but 14 can be get by using two 7 cents, total of 2 coins.

   2) denominations set = {1, 8, 20}
   to pay 24 cents
   our algorithm will return 1 coin of 20 and 4 coins of 1, total of 5coins but 24 can be get by using three 8 cents, total of 3 coins.

   So, basically this algorithm will always work when denominations set has multiples coin

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

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