Can someone help me with these Greedy Algorithm question? Please walk me through
ID: 3579460 • Letter: C
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)Explanation / Answer
Algorithm:
1) intialize the int variables hundrad,twenty_five,ten,five,one with zero then read the input from user and store it in int variable amount
2)if amount>=100 //to check the given amount is greater than hundrad, this is done because if value is greater than //hundrad , we can pay with hundrad cents which will be very less in number when we pay with other coins
then
hundrads=amount/100 //to know how many hundrad coins required
and
amount=amount%100// the remaing amount that cannot be paid using hundrad is calculated
3)if amount>=25
then
twenty_five=amount/25 and amount=amount%25 //this wiil calculate number of 25 cents required and remaining //amount
4)if amount>=10
then
ten=amount/10 and amount=amount%10 //this will calculate no.of 10 cents coins and remaining amount to be paid
5)if amount>=5
then
five=amount/5 and amount=amount%5
6)one=amount
7)print the coins needed are
hundrad 100 cent coins, twenty_five 25 cent coins, ten 10 cent coins ,five 5 cent coins and one 1 cent coins
---->the sets that do not satisfy the greedy algorithm
1)1,3,5
for 6 cents-->this can be two three cent coins or 1 five cent and 1 cent coin
so we cannot determine which one to use.
2)1,2,3
for 4 cents-->two 2 cent coins or one 1 cent and one 3 cent coin