What are Greedy Algorithms?
Greedy Algorithms are simple, easy to implement and intuitive algorithms used in optimization problems. Greedy algorithms operate on the principle that if we continue making the locally optimal choice in each subproblem we will form the global optimal choice for the entire problem.
Properties for Greedy Algorithms
Greedy Algorithms can be applied to problems following two basic conditions:
- Greedy Choice Property: A global optimum can be reached by selecting the local optimums.
- Optimal Substructure Property: A problem follows optimal substructure property if the optimal solution for the problem can be formed on the basis of the optimal solution to its subproblems
Where to use Greedy approach?
Let’s discuss this by trying to solve a problem: Fractional Knapsack!
Question: You are given weights and values of N items and a knapsack that can hold upto knapsack_capacity weight units. You need to find the maximum total value we can get into the knapsack.
Now, what would you do in this case? Which items will you choose the elements and how will you choose them? How would you evaluate whether an item should be put in a knapsack or not?
Well, obviously the elements giving us a higher value with respect to its weight should be chosen. Therefore, we would consider the value/weight ratio to evaluate whether we need to put the item in the knapsack or not. In simple words, we are basically following the unitary method as our evaluation criteria!
This is the greedy choice! We won’t try putting different combinations of items into the knapsack and then check which combination of items yields us the maximum value. We will sort them on the basis of the value/weight ratio and select elements with higher ratios to fill the knapsack.
The problem also follows the optimal substructure property.
Pseudo-Code
bool comp(Item a, Item b)
{
return (a.value / a.weight) > (b.value / b.weight)
}double fractionalKnapsack(Item arr[], int N, int knapsack_capacity)
{
sort(arr, arr+N, comp) int curr = 0
double ans = 0.0 for( i = 0 to N-1 )
{
if ( curr + arr[i].weight <= knapsack_capacity )
{
curr += arr[i].weight
ans += arr[i].value
} else
{
double rem = knapsack_capacity - curr;
ans += arr[i].value * (rem / arr[i].weight)
break
}
}
return ans
}Where you shouldn’t use Greedy approach?
Knowing where not to use Greedy is really important because if optimal substructure property is followed and the greedy choice property is not applicable, you will reach a wrong answer.
Question: Given a tree, you need to find the path from the root to any leaf that has the maximum sum of node values along the path.
If you form the path by choosing the maximum value child at each level(The Greedy Choice!), you will end up with the path 5->7->2 But we can see that clearly 5->3->17 is the path with the maximum sum of values. We assumed the greedy choice property applies in this problem and ended up with the wrong answer! We need to traverse every path and check the sum once we reach the leaf and compare the path sum with the maximum global sum we reached until then.
Pseudo-Code
int findMaxRootToLeafPath(TreeNode root)
{
if ( root == NULL )
return 0;
int left_sum = findMaxSumPath(root.left)
int right_sum = findMaxSumPath(root.right) return root.val + max(left_sum, right_sum)
}★ Try analyzing the complexities of the above code.
Examples
Question: Job Sequencing Problem → You are given deadlines of N jobs. Each job has a profit associated with it. Every job takes a single unit of time. Find the maximum profit you can get by sequencing the jobs.
For example, You are given the following list of jobs →
JobID | Deadline | Profit
------|-----------|--------
a | 2 | 100
b | 1 | 19
c | 2 | 27
d | 1 | 25
e | 3 | 15You need to find the maximum profit that can be yielded by sequencing the jobs optimally.
We can clearly see that there are two jobs with deadline 1 and two jobs with deadline 2 . This means that out of these four jobs, we will only be able to complete two jobs on time. Either one task with deadline 1 and one task with deadline 2 or both tasks with deadline 2. We will choose the two tasks with deadline 2 because that yields the maximum profit for us.
This helps us in forming a strategy to solve the problem. Since we are always going to prioritize profit yielded above everything else, we shall first sort the array according to the profit the job yields. We will then pick every job and see if it can be fitted into our schedule. This way, the sequence we form will yield the greatest profit.
Pseudo-Code
int jobSequencing(Job arr[], int N)
{
// Job with highest profit will come first
sort(arr, arr+N, comp)
// There are N jobs, means there should be N free slots
// Array stores if slot[i] is allocated to a job or not
bool slot[N] // Default Value: False
int max_profit = 0
for(i = 0 to N-1)
{
// start denotes the highest slot that could be
// allocated to the job
int start = min(arr[i].deadline, N)
for(j = start to 0, decrement of -1)
{
if(slot[j] == false) // The slot is free
{
slot[j] = true
max_profit += arr[i].profit
break
}
}
}
return max_profit
}Do you understand the concept of Greedy Algorithms now? Can you implement the same on different problems now?
Let us try solving one more problem with Greedy Approach.
Question: Minimum number of coins required → We have an infinite supply of coins of these denominations: { 1, 2, 5, 10, 20, 50, 100, 500, 1000}. Given a value C , find the minimum number of coins that reach the sum of C .
When you need to give someone a change amounting to C and you have an infinite supply of given denominations. How would you proceed to make the change?
You would pick the greatest denomination you have that is less than C , say D , and then repeat the same process for amount C - D . This should ideally help you reach the sum of C with the minimum number of coins.
Pseudo-Code
int findMinimumNumberOfCoins(int C)
{
int denominations = {1, 2, 5, 10, 20, 50, 100, 500, 1000}
int N = 9
int count = 0
for( i = N-1 to 0 )
{
while( denominations[i] < C )
{
C = C - denominations[i]
count += 1
}
}
return count
}First, let’s discuss this code a little. Can you optimize this code even more? ( Hint: How many times will the inner while loop run?)Well, we can →
- increase the count in one go. count += ( C/denominations[i] )
- assign C = C % denominations[i]
Try to dry run this code with a few examples. Does it give the right answer every time?
Yes, it does. Because for this particular case , the greedy choice property applies!
How can the problem be tweaked so the greedy choice property cannot be applied anymore?
If the value in denominations array are changed to be not so well distributed like let the denominations array be {1,5,6,10,20,25}, the greedy approach will not yield the optimal result. Let’s take some examples →
- C = 12, Greedy Choice: (10,1,1), Optimal Choice: (6,6)
- C = 24, Greedy Choice: (20,1,1,1,1), Optimal Choice: (6,6,6,6)
As we can see, the greedy choice property didn’t hold in the above example. Therefore, we always need to check whether the greedy choice property applies to a problem or not. In the example, the set of denominations was pre-defined and greedy choice property could be applied to it and therefore the code yields correct output for any input. Normally, for a general set of denominations, we use a dynamic programming approach.
Try solving the problem using a Dynamic Programming Approach!
What if both DP and Greedy can be applied to the same problem? Which method should you use? Dynamic Programming divides the problem into several sub-problems, finds the solution to all sub-problems and then selects the most optimal answer whereas, in a Greedy Approach, we choose the local optimum at each step and therefore, solve only one problem.
Hence, Greedy is faster than Dynamic Programming when both can be applied to the same problem! But always check if the greedy choice property holds or not.
Critical ideas to think!
- What are some other problems you can solve using the Greedy Approach?
- Try finding problems which you can solve using both Greedy and Dynamic Programming and analyze the differences in both approaches.
- How would you verify the Greedy Choice Property in problems?
