Explain Greedy Algorithm. Find Minimum number of Coins

 

Explain Greedy Algorithm to find Minimum number of Coins

A greedy algorithm is a strategy that always chooses the locally optimal solution at each step, hoping to find a globally optimal solution by the end. In other words, it makes the best possible decision at each step without considering the long-term consequences.

Let's consider an example problem to better understand how a greedy algorithm works. Suppose we have a set of n coins with different denominations, and we want to make change for a given amount C using the minimum number of coins.

Suppose we need to make change for 67 cents using the following coins:

• 25 cents
• 10 cents
• 5 cents
• 1 cent

1. Sort the coins in descending order of denomination: 25 cents, 10 cents, 5 cents, 1 cent.
2. Start with the largest coin denomination, which is 25 cents. Subtract 25 from 67, leaving 42.
3. The largest coin denomination that is less than or equal to 42 is 25 cents. Subtract 25 from 42, leaving 17.
4. The largest coin denomination that is less than or equal to 17 is 10 cents. Subtract 10 from 17, leaving 7.
5. The largest coin denomination that is less than or equal to 7 is 5 cents. Subtract 5 from 7, leaving 2.
6. The largest coin denomination that is less than or equal to 2 is 1 cent. Subtract 1 from 2, leaving 1.
7. The largest coin denomination that is less than or equal to 1 is 1 cent. Subtract 1 from 1, leaving 0.

PROGRAM OF PYTHON TO FIND MINIMUM NUMBER OF COINS:-

def coin_change(m):

 lis=[50,20,10,100,5,1]

 lis.sort(reverse=True)

 res=[]

 for i in lis:

  while m>=i:

   m-=i

   res.append(i)

 return res

print(coin_change(111))

OUTPUT:-

[100, 10, 1]