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)

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

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

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