Greedy Algorithm Problem With Solution Set-1

I am starting a series where we will discuss problems on the Greedy Algorithm along with their solution and explanation. We will start from easy Leetcode that are based on greedy algorithm problem first and accordingly, we will increase the level.

Today I am going to discuss two problems based on Greedy Algorithms. The problems are easy to level problems but they are useful in understanding the Algorithm better.

Leetcode 1029 : Two City Scheduling

There are 2N people a company is planning to interview. The cost of flying the ith person to city A is cost[i][0] and the cost of flying the ith person to city Bis cost[i][1].

Return the minimum cost to fly every person to a city such that exactly N people arrive in each city.

Example 1:

Input: [[10,20],[30,200],[400,50],[30,20]]
Output: 110

Explanation: The first person goes to city A for a cost of 10. The second person goes to city A for a cost of 30. The third person goes to city B for a cost of 50. The fourth person goes to city B for a cost of 20. The total minimum cost is 10 + 30 + 50 + 20 = 110 to have half the people interviewing in each city.

Note:
1 <= costs.length <= 100
It is guaranteed that costs.length is even
1 <= costs[i][0], costs[i][1] <= 100

Analysis of Problem Statement

So, let us understand the problem statement more clearly, there are 2N people in a company and they all have to travel to two cities (let say city A and B) for their work.

The travel cost of each person to both cities are given. You have to pick N people for each city such that cost of travel is minimum.

Here our constraint is travel cost and we have to minimise it.

Let us understand take few examples,

Two city scheduling

In the above example, there are 4 people in a company and travel cost of all employee to cities A (yellow) and B (green) are given respectively.

Output : 110

The 1st and 2nd person visit city A at the cost of 40 (10+30) and 3rd and 4th person visit city B at the cost of 70 (50+20).

NOTE, since N = 4 in the above case, 2 employees visit city A and 2 visit city B.

Let’s take another example,

greedy algorithm problem

In this example also, there are 4 people in a company and for every employee traveling to city A is cheaper than city B but we can’t send every employee to city A.

We have to make sure that two people will travel to city A and two people will travel to city B at a minimum cost.

Output : 20 + 15 + 40 + 30 = 105

This is the minimum cost where we sent 1st & 4th employee to city B and 2nd & 3rd to city A.

Hope Problem statement is clear to you, it is highly recommended please try it yourself before moving to the solution.[greedy algorithm problem]

Approach to the Problem

Let us discuss how you will approach this greedy algorithm problem because my motive is not to just post you the solution, I want you all to understand how to think of the approach to tackle the problem.

The first intuition which comes in our mind to sort the each pair according to travel cost to city A then send first N/2 person to city A and rest to city B.

Yes you can think of this approach but my friend the second example is already sorted according to travel cost to city A.

greedy algorithm problem

Our previous approach will not give you the minimum cost. Just think of another approach. Before that let me ask you one question,

What do you actually want to do..??

You want to send that employee to city A, where sending the same employee to city B is costlier.

But in the above example, for every employee, travelling to city A is cheaper, so in this situation, you want to send those employees to city B were travelling to city B is not much costlier than travelling city A. I mean where difference between both the prices is minimum.

Well mate! Are you thinking this approach, so let me tell you that you are thinking in the right direction. Just write the code accordingly.

Greedy Solution

So, the approach we discussed above is actually a greedy approach. We are greedily trying to manipulate the constraints so that it can minimise our overall cost.

So, I think now its our time to discuss the solution. The approach to its solution is similar to what we have discussed.

As we know if the difference of both the travel cost (A – B) is too high then we will send that employee to city A and if difference is low, we will send that employee to city B. This is what we have seen before.

Let’s see the code for better understanding,

static bool cmp(vector<int> &x, vector<int> &y)
{
    return (x[1] - x[0]) > (y[1] - y[0]);
}

int twoCitySchedCost(vector<vector<int>>& costs) {

    sort(costs.begin(),costs.end(),cmp);
    int res = 0;

    for(int i=0 ; i < costs.size() ; i++)
    {
        if(i < costs.size()/2)
        {
            res+=costs[i][0];
        }
        else
        {
            res+=costs[i][1];
        }
    }

    return res;
}

Yes, in the above code we sort the vector of vector according to difference of travel cost (Travel cost to city A – Travel cost to city B) in descending order.

So now we will send first N/2 employees to city A whose (A – B) difference is more and rest N/2 to city B.

So now we are actually sending all the employees to both the cities at minimum cost which was asked in the problem.

Hope this Greedy Approach is clear to you guys. We will discuss one more question in this post. So don’t feel if you can’t solve this problem. Just learn how to approach the problem and that’s how you will improve.

Now let’s move to our next Question.

Leetcode 122 : Best Time to Buy and Sell Stock II

Another Greedy algorithm problem Say you have an array price for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times).

Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).

Example 1:

Input: [7,1,5,3,6,4]
Output: 7

Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.

Example 2:

Input: [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.

NOTE that you cannot buy on day 1, buy on day 2 and sell them later, as you are engaging multiple transactions at the same time. You must sell before buying again.

Example 3:

Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

Constraints:
1 <= prices.length <= 3 * 10 ^ 4
0 <= prices[i] <= 10 ^ 4

Analysis of Problem Statement

You are given an array of prices where ith element is the price of a given stock on day i.

Like for example, if the price of one share of the stock is Rs 5 on day 1 and its price is Rs 7 on day 2, so you can buy that share on day 1 and can sell it on day 2 to earn Rs 2 profit.

Here you are given an array list and you can buy and sell the share to earn profit. Now you have design the algorithm such that you can maximum profit.

Also you can one buy and sell one share at a time.

Let’s take an example,

Like in the above example, if you buy a share on day 0 (7) and sell it on day 1 (1), you have to suffer a loss. So it’s better not to buy share on day 0.

Now I think problem statement is clear, you have to buy and sell share to earn maximum profit.

Output of above example : 7

In the above example, you can buy stock on day 1 (1) and can sell it on day 2 (5) to earn a profit of 4 and similarly if you buy a stock on day 3 (3) and sell it on day 4 (6), you will earn a profit of 3 from that share. So maximum profit you can earn is (4 + 3 = 7).

Hope problem Statement is clear.

Greedy Approach

If you observe carefully, above problem is an example of Greedy Algorithm where constraint is profit and you have to maximise it.

Now if you observe carefully, you can earn a profit only when the selling price is more than cost price.

So Greedily, we will find if price of share on current day is more than previous day. If yes, then we will count that share and we will store the profit.

We will move this way and at last we will get the maximum profit which we can earn.

Let’s see the code,

int maxProfit(vector<int>& prices) {

    int s = 0;

    for(int i = 1; i < prices.size(); i++)
    {
        if(prices[i] > prices[i-1])
        {
            s = s + prices[i] - prices[i-1];
        }
    }
    return s;
}

It is a very simple code and I don’t any explanation is required to understand the code.

That’s all folks for today. We have discussed two basics Greedy Problems and also discussed the approach. We will solve more problems of higher difficulty later. So stay tuned.

Tagged : /

0-1 Knapsack Problem

We have already discussed the Fractional Knapsack Problem in the previous post of the Greedy Algorithm tutorial. In this post, we will discuss another famous problem 0-1 Knapsack Problem.

0-1 Knapsack problem is similar to Fractional Knapsack Problem, the 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 values in the knapsack.

NOTE here we cannot collect items partially. we only have two options, whether to pick the item completely or leave the item. This is why this problem is called the 0-1 Knapsack Problem, either you pick the item or don’t pick it.

Consider an example of a knapsack containing coins, we cannot break or divide a coin partially, either we have to take the coin or leave it.

I hope
the Problem Statement is clear to you.

Analysis of the Problem Statement

Let us understand the problem statement more clearly by taking an example.

0-1 knapsack problem
0-1 knapsack problem

In this above example, the optimum solution would be by taking item 2 and item 4, the output will be 90.

NOTE that here we have only two choices, either to pick the item or leave the item.

Naive Solution of 0-1 Knapsack problem

As we know that we have only two choices, and we have to collect maximum possible values in the knapsack within the knapsack capacity, we will use recursion to solve this problem. We will run recursion from backward.

This problem is similar to the problem of finding all possible subsequences of a string.

Let’s see the recursive code for 0-1 knapsack problem,

int knapsack(int weight[], int value[], int capacity, int n)
{
        if(n == 0 || capacity == 0) return 0;

        if(weight[n-1] > capacity) {
              return knapsack(weight, value, capacity, n-1);
        }

       else {
             int case1 = knapsack(weight, value, capacity, n-1);
             int case2 = value[n-1] + knapsack(weight , value, capacity - weight[n-1], n-1);

             return max(case1, case2);
       }
}

Let us understand the code clearly, initially we have weight[ ], value[ ], capacity, and n (number of items).

It’s clear that if (weight of the item > capacity), we will not consider that item as it violates our capacity limit.

Now, we already know that there are only two cases possible, so we will consider both cases –

(i) In the first case, we will not consider the nth item, so we will simply call recursion to the remaining (n-1) items.

(ii) In the second case, we will consider the nth item. So after consideration, capacity will reduce to (capacity – the weight of that item) and we will also add up its value to the result.

We will again call recursion to the remaining (n-1) items by updating other parameters.

Time Complexity of Recursive Solution : O(2^n)

Let us understand this recursion by considering the above example,

0-1 knapsack problem
0-1 knapsack problem

Now let run the recursion for the above example,

I hope it’s clear how Recursion is taking place.

We can observe that there is an overlapping subproblem in the above recursion and we will use Dynamic Programming to overcome it.

Dynamic Programming Solution of 0-1 knapsack problem

As recursion proceeds, we observe that there are overlapping subproblems present and it is no point to solve the same subproblems again and again.

Let us now see the DP code,

int dp[n+1][capacity+1] = {-1,-1,.., -1};

int knapsack(int weight[], int value[], int capacity, int n)
{
        if(n == 0 || capacity == 0) return 0;
        if(dp[n][capacity] != -1) return dp[n][capacity];

         if(weight[n-1] > capacity) {
                 dp[n][capacity] =  knapsack(weight, value, capacity, n-1);
         }

         else {
                int case1 = knapsack(weight, value, capacity, n-1);
                int case2 = value[n-1] + knapsack(weight , value, capacity - weight[n-1], n-1);

                dp[n][capacity] = max(case1 + case2);
         }
         return dp[n][capacity];
}


This is a Memoization based Solution (Top Down). It is similar to the recursive solution only difference is that we are storing the solution of subproblems into some array or hash map so that whenever we need the solution of that subproblem again, we can use this data instead of calculating it again.

Time Complexity of Top-Down Solution: O(n.capacity)

Bottom-up (Tabulation) based Solution

This Solution is similar to top-down solution, the only difference is that we fill an array in a bottom-up approach, which means we first fill the array considering that there is only one item available to us, then we fill the array considering that there are only two items available to us and this way we fill the entire 2-D array.

Let’s us see the code,

int knapsack(int weight[], int value[], int capacity, int n)
{
	int dp[n+1][capacity+1];
	memset(dp, 0, sizeof(dp));

	for(int i = 1; i <= n; i++)
	{
		for(j = 1; j <= capacity; j++)
		{
			if(weight[i-1] > j) dp[i][j] = dp[i-1][j];
			else {
				dp[i][j] = max(value[i-1] + dp[i-1][j-weight[i-1], dp[i-1][j]);
                             }
                }
        }
        return dp[n][capacity];  
}

Let us understand the code more clearly, we have created a dp[][] 2D array of size [n+1][capacity+1], one extra space for storing base condition and after that, we have followed the same steps that we have followed in memoized based approach.

Let us understand it by an example,

0-1 knapsack problem
0-1 knapsack problem

We will make a table for this above example,

0-1 knapsack problem
0-1 knapsack problem

Here row denotes the item and column denotes the capacity.

Let us understand the table more clearly,
dp[1][5] denotes that by considering the first item, maximum how much value we can earn by a knapsack of capacity 5.
dp[3][7] denotes that by considering the first 3 items, maximum how much value we can earn by a knapsack of capacity 7.

We will get the answers to the above Question by following the bottom-up Dynamic Programming Algorithm.

Time Complexity : O(n.capacity)

I hope this problem statement(0-1 knapsack problem) and its DP solution is clear to you all.
That’s all Folks..!!!

Try some sliding window technique problem here

Tagged : /

Greedy Algorithm with Examples

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 &lt; 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&gt;d1) ;
}
double knapsack(vector&lt;pair&gt; &amp;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 &lt; items.size(); i++)
	{
		if(weight + items[i].first &lt;= 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 : / /