### 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.

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.
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
<<endl;

cin>>number;

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

cin>>maxtime;

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

"
<<(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
<<numberOfThings<<endl;

return 0;

}

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

Output:

5

Enter Maximum time

7

3

2

1

3

2

Maximum Number of tasks Completed = 3

#### More Articles of M Mounika:

Name Views Likes
C++ Inplace Rotate square matrix by 90 degrees 788 0
C++ Introduction to Greedy Approach 2518 2
C++ Gold Mine Problem 1294 0
C++ Anagram substring Search 584 0
C++ Segment Trees 819 2
Disjoint Data Structures 597 1
C++ Greedy Approach-Activity Selection Problem 2806 1
C++ Trie Datastructure 3152 1
C++ Minimum Removal of Characters from string to make its permutation as palindrome 594 0
C++ Greedy Approach Minimum number of coins 1731 0
C++ Greedy Approach-Huffman Codes 5545 1
C++ Manachars Algorithm 1763 0
C++ smallest substring with maximum distinct characters 1436 0
C++ Trie Cost of Data 1186 1
C++ Greedy Approach Maximum product Subset 1006 1
C++ Greedy Approach Maximum height Pyramid 1022 1
C++ Greedy Approach-Egyptian Fractions 1456 0
C++ String Matching(KMP Algorithm) 996 0
C++ K Centers Problem 1240 0
C++ Find Non Repeating Elements in Array 1070 0
C++ Greedy Approach Minimum Product Subset 1170 1
C++ Merge K Sorted Arrays 662 0
C++ Number of Bracket Reversals needed to make expression Balanced 322 0
C++ Basics of String Manipulation 411 1
C++ Problem On Disjoint Data Structures 466 0
C++ Find Nth Catalan Number 1007 0
C++ Greedy Approach String lexicographically largest subsequence 1130 0
C++ Merge Two Binary Trees 705 0
C++ Remove Duplicates From String 3402 0
C++ Minimum characters added at front of string in palindrome conversion 413 0
Disjoint Data Structures Part2 420 0
C++ Greedy Approach Prims MST 1146 1
C++ Greedy Approach N-array maximum sum 776 1
C++ String Matching(Naive Algorithm) 1816 0
C++ Flood Fill Algorithm 2833 0
C++ WildCard pattern matching 2658 0
C++ String Matching(Z Algorithm) 640 0
C++ Meta Strings 685 0
C++ Sum of Numbers From Root To Leaf Paths 675 0
C++ Greedy Approach Lexicographically largest subsequence 902 0
C++ Disjoint Data Structures Part3 377 0
C++ Sieve Of Erastosthenes 534 0
C++ String to Palindrome with Append Function 579 0
C++ Search String in Grid 1583 0
C++ Greedy Approach Policemen Catch Thieves 2047 1
C++ Smallest window with all characters in string 901 0
C++ Greedy Approach Fractional Knapsack 2852 1
C++ Disjoint Data Structure Cycle Detection 569 0
C++ Segmented Sieve (Print Primes In a Range) 1940 0
C++ Greedy Approach Krushkals MST 946 1