SITUATIONS WHERE GREEDY APPROACH FAILS.....
Situations where greedy approach fails.....
Greedy approach is one of the important approaches for the the optimisation programming problems. But there are lots of such situations where Greedy approach fails to give the optimum solution . Before going to the limitations of the Greedy approach , First discuss How actually the greedy approach works......
Let assume you went to a Mall , where an offer was going on. The condition was that you will have a given time period during which you have to collect as many goods , you get a huge discounts on those good. What will your reaction during that given time period ?? Most of us choose those goods which are costly and useful. For each attempt of selection , we will intend to select those goods which are most valuable and important for us.
The approach that we will use in the above situation is actually known as Greedy approach. This approach is used to solve different types of coding problems which have direct or indirect applications in real life problems.
Lets solve a problem using Greedy approach.....
Assume you have to make a collection of Rupees 28 using three types of coins whose values are 1, 2, 5 respectively. Your job is to collect coins in such a way that number of coins should be minimum . It is given that you can take any coin any number of times.
Think Greedy !!!!!!
To make the number of coins minimum , we have to choose those coins as many possible times whose value is maximum. To make 28 , we start with coin whose value is 5.
The coins in the solution are ........ 5 5 5 5 5 2 1 .
Here we chose 5(coin with maximum value) five times then chose 2(coin with second maximum value) one time and 1 one times... and the set of coins give the optimum solution.
But..... Apply the Greedy approach for same problem using 18 instead of 28 and use 5 and 7 in place of 2 and 5 .
Greedy approach will give the answer 7 7 1 1 1 1
But after thinking more we get the answer 7 5 5 1 . which is more optimum than previous one !!!
Lets take an another example.....(IF YOU'RE USING SMARTPHONE PLEASE ROTATE IT IN LANDSCAPE MODE FOR BETTER VIEWING)...
Assume there is a delivery boy whom daily given different wages for three specific cities. For a specific couple of day wage list is as given below...
city 1 city 2 city 3
Day1 wage -> 12 50 19
day2 wage -> 23 100 45
The delivery boy can choose any city for a single day but the condition is that delivery boy can't work in any city for two consecutive day that means if he works in city 1 for Day1 then he can't choose city 2 for the Day2 .
Our job is to choose two days in such a way that delivery boy could Earn maximum possible wage.
What greedy approach says .... Choose that city for Day 1 that give maximum earnings and again apply same for Day 2. By greedy approach ... for Day 1 ,we've to choose city 2 and since by the given condition we can't choose city2 for Day 2 so by greedy we'll choose city 3. The total wage for these two days by the Greedy approach will be 95 .
But after thinking more logically , We'll find that if we choose city3 and city2 , delivery boy will get total wages of 119.
Hence , for each optimum problem we can't apply Greedy approach . Greedy approach is applicable for only those problems for which future moves can be predictable . There are a lots of standard problems where Greedy approach works efficiently . Some of them are ....
Prim’s Minimum Spanning Tree (MST)
Dijkstra’s shortest path algorithm
Situations where the Greedy Approach fails ... , The concept of Dynamic programming comes into the picture.......
Wow....you explained in such an easy way💜
ReplyDelete