Greedy Algorithm

“Greed is good,” Michael Douglas exclaims in front of a room full of stockholders in the 1980s classic Wall Street. Greed has the upper hand… Greed is effective.”

the greedy algorithm is the most simple, ingenious, and easy to implement algorithm used in optimizing problems is the Greedy Algorithm.It is based on the idea that even if we continue to make the locally optimal choice in and subproblem, we would ultimately converge at the best solution for the true problem.

How to decide which choice is optimal?

Presume you get an objective function that needs to be optimised (enhanced or reduced) at a given phase.The Greedy algorithm only has one opportunity to find the correct response, so it never reverts straight and overturns the decision.

In certain instances, greedy algorithms are really useful, including Huffman coding, that is used to compact data, and Dijkstra’s algorithm, that is used to find the best route via a graph.

But, the greedy algorithm doesn't always yield the best result. It actually achieves this by picking the current highest number at each step.The greedy algorithm, on the other hand, struggles to find the largest sum because it makes decisions based solely on the knowledge available at any given time, with no consideration for the larger problem.

History of Greedy Algorithm

In the 1950s, greedy algorithms were proposed for a variety of graph walk algorithms.

The algorithm for generating minimal spanning trees was created by Esdger Djikstra.

Prim and Kruskal developed optimization strategies mainly focused on minimizing path costs along weighted routes during the same decade.

In their classic introduction to algorithms book from the 1970s, American researchers Cormen, Rivest, and Stein suggested a recursive substructuring of greedy solutions.

In2005, the NIST records listed the Greedy search model as a totally different form of optimization strategy.

To date, web-running protocols like open-shortest-path-first (OSPF) and several other network packet switching protocols have used the greedy technique to reduce network time.

What are the properties of the Greedy algorithm?

1. Greedy option property: Greedy option property applies to a fact that the best solution at each stage contributes to the best solution overall.
2. Optimal Structure: The problem is assumed to have the optimal substructure property if the optimal solutions of the sub-problems contribute to the optimal solution of the problem.

Greedy algorithm’s Benefits and Drawbacks:

Benefits:

1. In the case of NP-Hard problems, greedy algorithms can be used for optimization or similar to optimization.
2. Usually, there are fewer time complexities.
3. The greedy approach is easy to implement

Drawbacks:

It’s not really ideal for Greedy problems where and subproblem, like sorting, requires a solution.

In these Greedy algorithms practice problems, the Greedy strategy can also be inaccurate, leading to a non-optimal approach in the worst-case scenario.

As a result, greedy algorithms have the drawback of not understanding what falls ahead of the new greedy state.

The downside of the Greedy strategy is depicted below:

The algorithm condition at position: 40 is inclined to take 29 as its next value in the greedy search displayed here as a tree (greater value greater greed). Its journey also draws to a close at 12. Which gives us the ranking of 41.

If, on the other hand, the algorithm followed a less-than-optimal route or used a commanding approach.

When do you use Greedy Algorithm?

We could use the greedy technique to solve a problem with the following properties:

1. The Greedy Choice Property states that locally optimal preferences will lead to a globally optimal solution.
2. Optimal Sub-Problem: According to this property, an optimal solution to the issue includes optimal solutions to its sub-problems.As a consequence, a globally optimal solution could be developed by combining locally optimal sub-solutions.

In general, greedy approaches are being used to solve optimization problems, or problems where we need to calculate the maximum or minimum of something to provide an optimal solution.

There are 2 kinds of approaches to an optimization problem:

1. Feasible Solution: An estimated answer (subgroup of solution) that meets the objective function, that might or might not contribute to the optimal solution.
2. A feasible solution either maximises or minimises the objective function is referred to it as an optimal solution.

How to create a Greedy Algorithm?

You have precisely T time to do a little fun stuff, and you want to do as many of them as possible because you are a very busy guy.

You’re provided an array A of integers, each of which represents the time it takes for anything to finish.You want to work out how many things you can get done with the period of time you have.

This is a straightforward Greedy-algorithm problem.You must greedily pick the items that will consume the least period of time to make in each iteration while retaining two variables: currentTime and numberOfThings.To conclude the equation, you’ll need to:

1. Sort the list A in ascending order instead of decreasing order.
2. Pick each to-do element one at a time.
3. To currentTime, add the time it will take to accomplish the to-do list.
4. Increase numberOfThings by one.

Continue doing this as long as currentTime is less than or equivalent to T.

Let A = {5, 3, 4, 2, 1} and T = 6

Following the sorting, A = {1, 2, 3, 4, 5}

Following the first iteration:

• currentTime = 1
• numberOfThings = 1

Following the second iteration:

• currentTime is 1 + 2 = 3
• numberOfThings = 2

Following the third iteration:

• currentTime is 3 + 3 = 6
• numberOfThings = 3

CurrentTime is 6 + 4=10, which would be higher than T after the fourth iteration.As a result, the response is 3.

Implementation:

#include <iostream>
#include <algorithm>
    using namespace std;
    const int MAX = 105;
    int A[MAX];

    int main()
    {
        int T, N, numberOfThings = 0, currentTime = 0;
        cin >> N >> T;
        for(int i = 0;i < N;++i)
            cin >> A[i];
        sort(A, A + N);
        for(int i = 0;i < N;++i)
        {
            currentTime += A[i];
            if(currentTime > T)
                break;
            numberOfThings++;
        }
        cout << numberOfThings << endl;
        return 0;
    }

Examples of Greedy algorithm

The Minimal Spanning Tree Algorithm of Kruskal

Huffman codes (data compression code)

The Minimal Spanning Tree Algorithm of Dijkstra

Work Scheduling Problem Graph-Vertex Cover Knapsack

Traveling Salesman Challenge with Prim’s Minimal Spanning Tree Algorithm

Graph — Map Coloring

Summary:

To conclude, the blog introduced the greedy theory and demonstrated how greedy optimization and recursion can support you in getting the optimum approach up to a point.