Introduction to Greedy Approach

In an algorithm design there is no one 'silver bullet' that is a
cure for all computation problems. Different problems require the use of
different kinds of techniques. A good programmer uses all these techniques
based on the type of problem. Some commonly-used techniques are:

1. Divide and conquer
2. Randomized algorithms
3. Greedy algorithms (This is not an algorithm, it is
   a technique.)
4. Dynamic programming 

What is a 'Greedy algorithm'?

A greedy algorithm, as the name suggests, always makes the choice that seems to be the best at that moment. This means that it makes a locally-optimal  choice in the hope that this choice will lead to a globally-optimal solution.

How do you decide which choice is optimal?

Assume that you have an objective function that needs to be
optimized (either maximized or minimized) at a given point. A Greedy algorithm
makes greedy choices at each step to ensure that the objective function is
optimized. The Greedy algorithm has only one shot to compute the optimal
solution so that it never goes back and reverses the decision.

Greedy algorithms have some advantages and disadvantages:

1. It is quite easy to come up with a greedy algorithm (or
   even multiple greedy algorithms) for a problem.
2. Analyzing the run time for greedy algorithms will generally be much
   easier than for other techniques
   (like Divide and conquer). For the Divide and conquer technique, it is not
   clear whether the technique is fast or slow. This is because at each level
   of recursion the size of gets smaller and the number of sub-problems
   increases.
3. The difficult part is that for greedy algorithms you have to work much harder to understand correctness issues. Even with the correct algorithm, it is hard to prove
   why it is correct. Proving that a greedy algorithm is correct is more of
   an art than a science. It involves a lot of creativity.  

How to create a Greedy Algorithm?

Problem Statement:

You are given an array A of integers,
where each element indicates the time a thing takes for completion. You want to
calculate the maximum number of things that you can do in the limited time that
you have.

Applying Greedy Strategy:

1. Sort the array A in a non-decreasing order.
2. Select each to-do item one-by-one.
3. Add the time that it will take to complete that to-do item into currentTime.
4. Add one to numberOfThings.
5. Repeat this as long as the currentTime is less than or equal to T.

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

After sorting, A = {1, 2, 3, 4, 5}

After the 1^st iteration:

• currentTime =1
• numberOfThings =1

After the 2^nd iteration:

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

After the 3^rd iteration:

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

After the 4^th iteration, currentTime is
6 + 4 = 10, which is greater than T. Therefore, the answer is 3

CPP Program for above described program along with output

 

//C++ Program using Greedy Approach for solving above problem

using namespace std;

#include<bits/stdc++.h>

int main(){

    vector<int> arr;

    int number,element,maxtime;

    int numberOfThings=0,currentTime=0;

    cout<<"Enter Number of
tasks"<<endl;

    cin>>number;

    cout<<"Enter Maximum time
"<<endl;

    cin>>maxtime;

    for(int i=0;i<number;i++){

        cout<<"Enter time for task
"<<(i+1)<<endl;

        cin>>element;

        arr.push_back(element);

    }

    sort(arr.begin(),arr.end());

    for(int i=0;i<number;i++){

        if((currentTime+arr[i])<maxtime){

            currentTime+=arr[i];

            numberOfThings+=1;

        }

        else{

            break;

        }

    }

    cout<<"Maximum Number of
tasks Completed = "<<numberOfThings<<endl;

    return 0;

}

----------------------------------------------------

Output:

Enter Number of tasks                                                      

5                                                                             

Enter Maximum time                                                                

7                                                                          

Enter time for task 1                                                          

3                                                                                 

Enter time for task 2                                             

2                                                                          

Enter time for task 3                                                      

1                                                                    

Enter time for task 4                                                   

3                                                                           

Enter time for task 5                                                  

2                                                                           

Maximum Number of tasks Completed = 3