Greedy Algorithm

A Greedy algorithm is one of the problem-solving methods which takes optimal solution in each step.

The Greedy algorithm attempts to take the best in each step and it doesn't care about the overall result.

Greedy Approach - "Living in the present. Don't overthink about the future".

Let's discuss greedy approach with minimum coin change problem.

Minimum Coin Change Problem

Given a set of coins and a value, we have to find the minimum number of coins which satisfies the value.

Example

coins[] = {5,10,20,25}

value = 50

Possible Solutions

{coin * count}

{5 * 10} = 50 [10 coins]

{5 * 8 + 10 * 1} = 50 [9 coins] goes on.

{10 * 5} = 50 [5 coins]

{20 * 2 + 10 * 1} = 50 [3 coins]

{20 * 2 + 5 * 2} = 50 [4 coins]

{25 * 2} = 50 [2 coins]

etc etc

Best Solution

Two 25 rupees. Total coins two.

25 * 2 = 50

Minimum Coin Change Problem Algorithm

1. Get coin array and a value.

2. Make sure that the array is sorted.

3. Take coin[i] as much we can.

4. Increment the count.

5. If solution found,

break it.

6. Otherwise,

follow step 3 with the next coin. coin[i+1].

4. Finally, print the count.

Example

coin[] = {25,20,10,5}

value = 50

Take coin[0] twice. (25+25 = 50).

Total coins = 2 (25+25)

Example

coin[] = {25,20,10,5}

value = 70

Take coin[0] twice. (25+25 = 50).

If we take coin[0] one more time, the end result will exceed the given value. So, change the next coin.

Take coin[1] once. (50 + 20 = 70).

Total coins needed = 3 (25+25+20).

In this approach, we are not bothering about the overall result.

We just pick the best option in each step and hoping that it might produce the best overall result.

Hence, this method called as the greedy approach.

Implementation of minimum coin change problem

Example

#include<stdio.h>
#define max  100

//arr - will have list of needed coins
int ans[max];

int findMinCoins(int coins[], int size,  int value)
{
    int i, count = 0;

    for(i = 0; i < size; i++)
    {
        //take as much from coins[i]
        while(value >= coins[i])
        {
            //after taking the coin, reduce the value.
            value -= coins[i];
            ans[count] = coins[i];
            count++;
        }
        if(value == 0)
            break;

    }

    return count;
}

int main()
{
    int coins[] = {25,20,10,5};
    int value = 105, i;

    //find the size of the coins array
    int size = sizeof(coins)/sizeof(coins[0]);

    int MinCount = findMinCoins(coins,size,value);

    printf("Total Coins Needed = %d\n",MinCount);

    printf("Coins are:\t");
    for(i = 0; i < MinCount; i++)
        printf("%d ", ans[i]);

    return 0;
}

When does the above greedy algorithm fail?

Let's take this scenario.

coins[] = {25,20,10,5}

value = 40

The greedy solution will be 25+10+5 [3 coins].

But the optimal solution will be 20+20 [2 coins].

So, we can't guarantee that the greedy algorithm always produces the overall best result.