C++ Introduction to Greedy Approach














































C++ Introduction to Greedy Approach



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
    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 1st iteration:

  • currentTime =1
  • numberOfThings =1

After the 2nd iteration:

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

After the 3rd iteration:

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

After the 4th 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


 


More Articles of M Mounika:

Name Views Likes
C++ Segmented Sieve (Print Primes In a Range) 146 0
C++ Sieve Of Erastosthenes 105 0
C++ Gold Mine Problem 247 0
C++ Merge K Sorted Arrays 97 0
C++ K Centers Problem 217 0
C++ Find Nth Catalan Number 289 0
C++ Inplace Rotate square matrix by 90 degrees 259 0
C++ Find Non Repeating Elements in Array 63 0
C++ Merge Two Binary Trees 90 0
C++ Sum of Numbers From Root To Leaf Paths 70 0
C++ Meta Strings 76 0
C++ Flood Fill Algorithm 375 0
C++ smallest substring with maximum distinct characters 113 0
C++ Smallest window with all characters in string 72 0
C++ Minimum Removal of Characters from string to make its permutation as palindrome 71 0
C++ Minimum characters added at front of string in palindrome conversion 55 0
C++ Number of Bracket Reversals needed to make expression Balanced 59 0
C++ String to Palindrome with Append Function 58 0
C++ WildCard pattern matching 61 0
C++ Anagram substring Search 55 0
C++ Manachars Algorithm 60 0
C++ Search String in Grid 66 0
C++ String Matching(Z Algorithm) 55 0
C++ String Matching(Naive Algorithm) 82 0
C++ String Matching(KMP Algorithm) 118 0
C++ Remove Duplicates From String 71 0
C++ Basics of String Manipulation 71 1
C++ Disjoint Data Structure Cycle Detection 73 0
C++ Problem On Disjoint Data Structures 65 0
C++ Disjoint Data Structures Part3 65 0
Disjoint Data Structures Part2 79 0
Disjoint Data Structures 81 1
C++ Segment Trees 292 2
C++ Trie Cost of Data 259 1
C++ Trie Datastructure 251 1
C++ Greedy Approach Minimum number of coins 457 0
C++ Greedy Approach Maximum height Pyramid 293 1
C++ Greedy Approach String lexicographically largest subsequence 202 0
C++ Greedy Approach Lexicographically largest subsequence 339 0
C++ Greedy Approach Prims MST 360 1
C++ Greedy Approach Krushkals MST 421 1
C++ Greedy Approach N-array maximum sum 314 1
C++ Greedy Approach Policemen Catch Thieves 539 1
C++ Greedy Approach Maximum product Subset 519 1
C++ Greedy Approach Minimum Product Subset 319 1
C++ Greedy Approach Fractional Knapsack 656 1
C++ Greedy Approach-Activity Selection Problem 653 1
C++ Greedy Approach-Egyptian Fractions 592 0
C++ Greedy Approach-Huffman Codes 815 1
C++ Introduction to Greedy Approach 924 2

Comments