Greedy Algorithms

Greedy Algorithms are a class of optimization algorithms that make locally optimal choices at each step of a problem to arrive at a globally optimal solution. The algorithm makes a series of choices that are locally optimal and hopes that these choices will lead to the globally optimal solution. The greedy algorithm does not consider the consequences of its choices beyond the current step. It makes the best choice at each step without worrying about how it affects future steps.

Let's take a real-life example of the change-making problem to understand the working of the greedy algorithm. Suppose you have to give change of 75 cents using coins of 1, 5, 10, and 25 cents. The goal is to use the minimum number of coins to give the change.

The greedy algorithm for this problem would work as follows:

Start with the largest coin value, which is 25 cents.
Check if the value of the coin is less than or equal to the remaining change amount.
If yes, subtract the value of the coin from the remaining change amount and add the coin to the solution list.
If not, move to the next smallest coin and repeat the above steps.

Using this algorithm, the optimal solution for the change-making problem would be two quarters and one twenty-five cent coin, for a total of three coins.

Advantages and Disadvantages of Greedy Algorithms

Advantages of Greedy Algorithms

Greedy algorithms are usually easy to understand and implement.

They are often faster than dynamic programming algorithms because they require less computational power and memory.

They are useful for solving optimization problems where the goal is to find the best possible solution with limited resources.

Disadvantages of Greedy Algorithms

Greedy algorithms may not always produce the optimal solution, as they make locally optimal choices that may not lead to the best global solution.

The optimal solution produced by a greedy algorithm is not guaranteed, and it may be suboptimal in some cases.

Greedy algorithms do not always work well for problems that involve complex constraints or dependencies.

Coin Change Problem using Greedy Algorithms

The greedy algorithm determines the minimum amount of US coins to give while making change. These are the steps a human would take to emulate a greedy algorithm. Greed manifests itself in this process because the algorithm picks the coins of highest value first.

In following example, we are trying to make change for an amount of 93 using the denominations [1, 2, 5, 10, 20, 50, 100, 500, 1000]. The program outputs the coins used to make the change, which are 50, 20, 20, 2, and 1, and the total number of coins used, which is 5. Here the target is to use least number of coins. Hence, we are selecting maximum number of largest posiible coins.

#include <stdio.h>

void changeMaking(int coins[], int n, int amount) {
    int i, j, count=0;
    printf("Coins used to make change: ");
    
    for(i=n-1; i>=0; i--) {
        while(amount>=coins[i]) {
            amount-=coins[i];
            count++;
            printf("%d ", coins[i]);
        }
    }
    printf("\nTotal coins used: %d", count);
}

int main() {
    int coins[] = {1, 2, 5, 10, 20, 50, 100, 500, 1000}; 
    int n = sizeof(coins)/sizeof(coins[0]); 
    int amount = 93; 
    
    changeMaking(coins, n, amount);
    
    return 0;
}

Output

Coins used to make change: 50 20 20 2 1
Total coins used: 5

Difference between Greedy, Divide and Conquer, and Dynamic Programming Algorithms

Greedy, Divide and Conquer, and Dynamic Programming algorithms are all techniques used for solving problems in computer science. Here are the main differences between them:

Greedy Algorithm

Makes locally optimal choices at each step in the hope of arriving at the globally optimal solution.
Does not consider the consequences of its choices beyond the current step.
Works well for optimization problems where the goal is to find the best possible solution with limited resources.

Divide and Conquer Algorithm

Divides a problem into smaller sub-problems that can be solved independently.
Solves the sub-problems separately and then combines the solutions to get the final result.
Works well for problems that can be divided into smaller sub-problems.

Dynamic Programming Algorithm

Breaks down a problem into smaller sub-problems and solves each sub-problem only once.
Saves the solutions to sub-problems in a table and reuses them to avoid redundant computation.
Works well for problems with overlapping sub-problems and optimal substructure.

When we should use Greedy Algorithms

When choosing an algorithm for a problem, it's important to consider the problem constraints and the trade-offs between different algorithmic approaches. Greedy algorithms are often a good choice when the problem exhibits the following characteristics:

Optimal Substructure: The optimal solution to a problem can be constructed from the optimal solutions of its subproblems. In other words, solving smaller subproblems optimally can lead to a globally optimal solution.
Greedy Choice Property: A locally optimal choice at each step can lead to a globally optimal solution. This means that we can make a choice that seems best at the current moment, without considering future choices, and still arrive at the best solution.
Efficient to Compute: Greedy algorithms are usually fast and easy to implement. They don't require complex data structures or sophisticated analysis techniques.

If a problem satisfies these characteristics, then a greedy algorithm may be a good choice. However, it's important to note that greedy algorithms don't always produce optimal solutions, and there may be cases where other algorithms such as dynamic programming or divide-and-conquer are more appropriate.

In general, greedy algorithms are often used when the problem involves finding the best or most efficient solution among a set of choices or options, and there are no constraints or restrictions on the choices that can be made. Examples of such problems include scheduling, sorting, and optimization problems.

Common Examples of Greede Algorithm

Below mentioned examples illustrate the diversity of problems where greedy algorithms can be applied to make locally optimal choices, aiming to achieve a globally optimal solution. It's important to note that while greedy algorithms are efficient and easy to implement, they may not always guarantee the most optimal solution for every problem.

Fractional Knapsack Problem: In the fractional knapsack problem, items with weights and values are considered, and the goal is to fill the knapsack with fractions of items to maximize the total value.

Dijkstra's Shortest Path: Dijkstra's algorithm finds the shortest path from a source vertex to all other vertices in a weighted graph, making locally optimal choices at each step.

Prim's Minimum Spanning Tree: Prim's algorithm constructs a minimum spanning tree for a weighted, connected graph by adding edges with the minimum weights at each step.

Kruskal's Minimum Spanning Tree: Similar to Prim's algorithm, Kruskal's algorithm constructs a minimum spanning tree, but it does so by adding edges in ascending order of weight.

Huffman Coding: Huffman coding is a compression algorithm that assigns variable-length codes to input characters, with shorter codes given to more frequent characters.

Activity Selection Problem: In the activity selection problem, a set of activities with start and finish times is given, and the goal is to select the maximum number of non-overlapping activities.

Coin Change Problem: Greedy algorithms can be applied to the coin change problem, where the goal is to make change for a given amount using the fewest possible coins.

Job Sequencing with Deadlines : This problem involves scheduling jobs with associated profits and deadlines to maximize the total profit while meeting the deadlines

Interval Scheduling: Interval scheduling involves selecting a maximum-sized subset of non-overlapping intervals from a set of intervals.

Previous
Dynamic Programming