Introduction
Welcome learners, We are now looking into what is greedy algorithm and how to use it. Generally we call this as greedy algorithm, but this is not an algorithm. This is a technique or method in which you implement algorithms.
This is a straight forward method, and the decision of solution is taken based on the information available in the problem. Greedy algorithm or technique helps us to write optimized code, it can be used in various problems. What do you think is this greedy algorithm? Look at the word “Greedy”, The literal meaning of it is wanting a lot more, this is exactly where you use this algorithm.
Where Greedy algorithm is used?
You will be given few problems where you need to maximize or minimize certain parameter, in few of such situation you can use greedy algorithm. I said few because greedy technique will not work always, but this is a very powerful technique. In order to implement greedy, you must be clear about the problem statement and you should decide on which parameter you should apply greedy. And most importantly few problems look like you can implement greedy, but you cannot. So before you should proceed with the greedy algorithm, you should be sure that greedy can be used for the given problem.
Example Problem
Let us consider the below problem statement
Q. You are given a container of certain capacity and also few bottles of different sizes. You are having water in you container and you need to fill as many bottles as possible.
Explanation :
Here, first you need to read the problem clearly and decide the parameter for which you need to apply greedy technique. In this problem there are not much confusing parameters. But it is straight forward that you need to maximize the number of bottles filled.
So bottles is your parameter.
You can approach this problem as: First you will fill the bottles with smaller size. So that you will remain with more quantity of water and can continue the same till the bottles are filled or the container is empty.
Greedy Algorithm implementation
For this, firstly you need to sort the sizes of bottles.
Secondly, you should start filling the bottles in the sorted order.
Maintain the count variable to keep track of how many bottles you filled so far.
If the container is empty or all the bottles are filled, you can print your count.
Python code for the above problem statement
In the above attached image you can see the greedy implementation for the problem statement.
Problems to practice
To know about importance of DSA, you can refer to Importance of DSA
