Greedy Algorithm with Examples

greedy algorithm

As the name suggests, this algorithm uses a greedy approach to tackle a problem. What do you mean by a greedy approach or a greedy algorithm?

Let’s take us a real-life example,

greedy algorithm

Let assume, you get Rs 50 every day for traveling to your college (single trip). There is an option that you can either take an AC bus which costs you Rs 50 per journey or you can take a non-AC bus which costs you Rs 25 per journey. AC bus takes 20 minutes less time than non AC bus to reach your college.

Now here two situation arises, what do you want ..?

Either you can take an AC bus so that you can reach your college soon, here you are saving your time or else you can take a non-AC bus so that you can save your money.

If you are greedy like me, you’ll obviously take a non-AC bus, so that you can save some amount of money or I can say to maximize your savings.

In our daily life, we have to deal with thousands of such situations, where we have to be greedy to maximize our constraints. Constraints can be anything like time, money, etc.

Technical Definition of Greedy Algorithms

In Computer Science, greedy algorithms are used in optimization problems. This algorithm allows you to take optimal decisions in every situation so that you can finally get an overall optimal way to solve the problem.

In the Greedy algorithm, our main objective is to maximize or minimize our constraints.

Let us take an example to make our concept more clear.

Let us assume you have an infinite supply of Rs 2, Rs 5 and Rs 10 coins and you have to use a minimum number of coins to pay some amount.

For ex, 25 can be paid using a minimum of 3 coins (two Rs 10 coins and one Rs 5 coin).
47 can be paid using a minimum of 6 coins (four Rs 10, one Rs 5, and one Rs 2 coins).

If you observe it, here we are using the Greedy method to solve this problem. Here the constraint is the number of coins and we have to minimize it.

How will we solve this problem ..?

We will first take the highest coin value so that we have to take less number of coins. When the amount value becomes less than the first coin value, we will take the second maximum coin value, this process will continue and at last, we will get the minimum numbers of coins which will be the optimum solution.

Code

int coinCount(vector v, int amt)
{
       sort(v.begin(), v.end(),greater());
       for(int i = 0; i < v.size(); i++)
       {
            int q = amt / v[i];
            count = count + q;
            amt = amt % v[i];
       }
       if(amt == 0) return count;
       else return -1;
}

So, in the above code, we first sort the coin value in descending order so that we can take the highest coin value first, then we simply counted how many coins will be required to pay the amount accordingly.

Time Complexity of the Algorithm: O(n log n)

Greedy Doesn’t work always

Now let us take another example, we have given coins of Rs 2, 7 and 10 and we have to pay Rs 16 with it.

The above Algorithm will give output 4 (one Rs 10 coin and three Rs 2 coins) but in actual optimum output is 3 ( two Rs 7 coins and one Rs 2 coin).

So Greedy Algorithm does not always give you optimal solutions but it works for some problems. Don’t worry we will discuss some problems.

Please NOTE that the Greedy Algorithm will provide a solution nearest to the optimal solution, so it is a useful algorithm. It will give you the solution with maximum probability and it can be really handy in some of the real-life problems.

Fractional Knapsack Problem

The Fractional Knapsack problem is a very famous Greedy Algorithm problem, we will discuss it to understand Greedy Algorithms more clearly.

Problem Statement says that we are basically given a set of items whose weights and values are given. We are also given a knapsack which has some capacity, the knapsack can’t store capacity beyond it.

Our aim is to collect maximum value in the knapsack, we can even collect some items partially. 

Explanation

In the above example, the constraint values and we have to maximize it. In this example, the optimum solution would be,

(i) Select item 2 first (weight = 20, value = 500).
(ii) Select item 3 (weight = 30, value = 400).
(iii) Lastly select item 1 partially, we will select only 20/50 part of it. 

Total weight = 70 
Value = 500+400 + (20/50)*600 = 1140.  We could have selected item 1 and item 2 completely, but the total value would have been 600 + 500 = 1100, which is not the optimal solution.

Let take another example,

(i) Select item 1 first (weight = 10, value = 60)
(ii) Select item 2 (weight = 20, value = 100) 
iii) Select item 3 partially, we will select (20/30) part of it. 

So total value = 100+60 + (20/30)*120 = 240, which is the optimal solution.

Hope the problem statement is clear, now think how will you solve this problem ??

Brute Force

The brute approach will be to find all the possible solutions and then select the solution with maximum value.

What are the possibilities here ?? 100 + 120 = 220 (Considering item 2 and item 3)
60 + 100 + (20/30) * 30 = 240 (Considering item 1, item 2 and item 3 partially)
60 + 120 + (10/20)*100 = 230 (Considering item 1, item 3 and item 2 partially) Of these possibilities,the maximum value is 240.

Brute Force will take exponential time complexity and it is not a good solution for this problem. Think of different approaches to solve this problem. Think of some Greedy approach.

Approach 1 : Greedy with respect to values

If we think to be greedy with respect to values, our approach will give output considering the highest value item first. (i) Select item 3 first(Capacity = 30, value = 120).
(ii) Select item 2 (Capacity = 20, value = 100). Hence total value = 220 and total capacity = 50.

This approach doesn’t give us the most optimum solution. We have to think of another approach.

Approach 2 : Greedy with respect to weights

If we think to be greedy with respect to weights, our approach will give output considering the highest weight item first. (i) Select item 3 first(Capacity = 30, value = 120).
(ii) Select item 2 (Capacity = 20, value = 100). Hence total capacity = 50 and total value = 220.

Both Approach 1 and Approach 2 give us the same solution. So both approach fails to give us an optimum solution.

Approach 3 : Greedy with respect to (value/weight) ratio

By this approach, we will pick an item which has highest (value/weight) ratio.

(i) Select item 1 first(Capacity = 10, value = 60).
(ii) Select item 2 (Capacity = 20, value = 100).
iii) Select item 3 partially, we will select (20/30) part of it.(Capacity = 20)

So total value = 100+60 + (20/30)*120 = 240, which is the optimal solution.
This is the main logic of the Knapsack Problem, we have used a greedy algorithm to solve this problem, but greedy with respect to (value/weight) ratio.

Code

bool ratio (pair p1, pair p2)
{
	double d1 = p1.second / p1.first;
double d2 = p2.second / p2.first;

return (d2>d1) ;
}
double knapsack(vector<pair> &items, int W)
{
	// vector pair stores weights, values of an item
	
sort(items.begin(), items.end(), ratio);

	int weight = 0, result = 0;
	for(int i = 0; i < items.size(); i++)
	{
		if(weight + items[i].first <= W)
		{
			weight += items[i].first;
			result += items[i].second;
		}
		else
		{
			int diff = W - weight;
			result += items[i].second * ((double) diff / items[i].first);
			break;
		}
	}
	return result;
}

This is how Greedy Algorithms work. I Hope Greedy Algorithms are clear to you all.

How will you identify a Greedy Algorithms Problem…?

Whenever you are given optimization problem like maximizing or minimizing some constraint, then Greedy Algorithm may give you the solution, you have to just think of some condition where you can apply Greedy, like in fractional knapsack problem, we applied greedy on (value/weight) and we got the optimal solution. In optimization problems where greedy algorithms fail, dynamic programming might be a better approach.

There are many optimization problems based Greedy Algorithm, we will discuss them later.

That’s all folks..!!!

Tagged : / /

2 thoughts on “Greedy Algorithm with Examples

Leave a Reply

Your email address will not be published. Required fields are marked *