We all have come across situations where, we had to be greedy to make a decision. Let it be with food items in a supermarket or just planning a trip with friends or family, so as to get the upper hand.The following topic, talks about an algorithm that works in a similar way to get things done…….
A Greedy algorithm is one that makes the best choice available at a moment. This means that it will take the best choice available to it at a local or basic level, hoping that this will be the best solution for solving the entire problem.
- A greedy algorithm makes greedy choices at each step to make sure that the objective function (main problem function) is performing optimally.
- A Greedy algorithm never backtracks and reverses its decisions. It has only one shot to make the best solution.
- It is relatively easy to make a greedy algorithm for a given problem.
- It is much easier to analyse the running time of greedy algorithms than of other techniques such as divide and conquer.
Unlike Dynamic Programming, which solves the subproblems using a bottom-up approach, a greedy strategy usually progresses in a top-down manner, making one greedy choice after another, reducing each problem to a smaller one.
Example
Fractional knapsack problem
In this problem, we can break the items into fractions to help us in maximizing the total value of the knapsack.
Consider we have ‘n’ objects. Object ‘i’ has a weight ‘wi’ and the knapsack has a capacity of ‘m’. If the fraction ‘xi’, where 0≤xi≤1 of the object I is placed into the knapsack, then profit ‘pi*xi’ is earned.
The objective is to fill the knapsack, such that a maximum profit is earned. The total weight of all the objects chosen should be less than or equal to the capacity of the knapsack, i.e., ‘m’.
Consider the following table with the following data:
No of fractions(n)=3, Capacity of knapsack(m)=20
Profits of items – p1=25, p2=24, p3=15
Weights of items – w1=18, w2=15, w3=10
|
Sl.No |
Fractions (x1,x2,x3) |
Weight ∑wixi |
Profit ∑pixi |
|
1. |
(1/2,1/3,1/4) |
16.5 |
24.25 |
|
2. |
(1,2/5,0) |
20 |
28.2 |
|
3. |
(0,2/3,1) |
20 |
31 |
|
4. |
(0,1,1/2) |
20 |
31.5 |
We observe that in case 2, our approach is to be greedy by profit. Whereas in case 3, our approach is to be greedy by capacity. In case 4, we try to strike a balance between the rate at which the profit increases and the rate at which the capacity is used.
A feasible solution is one which solves the basic requirement of the algorithm. Whereas an optimal solution is one which best solves the requirements of the algorithm. In the above problem, the requirement is to get maximum profit by using the fixed amount of space available to us. Therefore, cases 1,2 and 3 are feasible solutions to the problem, but case 4 is the optimal solution as we receive the maximum profit in this case for the given conditions.
To solve this problem, a brute-force solution would be to try all possible subsets with all different fractions but that will be too time consuming.
Instead we use the Greedy approach. The basic idea of greedy approach is to calculate the ratio of profit/weight(pi/wi) for each item and sort the item on basis of this ratio. Then take the item with highest ratio and add it to the knapsack. We then check the next item with the highest ratio and add it to knapsack according to the space available. This process is repeated till there is space available in the knapsack. This method will give us the optimal solution to the problem.
Algorithm
for i←1 to n do x[i]=0.0
{
u=m;
for i←1 to n do
{
If( w[i]>u) then break
X[i]=1.0; u=u-w[i];
}
If( i≤n) then
X[i]= u/w[i];
}
In conclusion, I would like to say that a greedy algorithm though difficult to implement, is an efficient problem solving approach. A greedy algorithm greatly reduces the time complexity of a given problem. Despite the benefits of greedy algorithms, it must be noted that most greedy algorithms may turn out to be incorrect.
I hope that this blog helped you in better understanding the functionality and workings of greedy algorithms.
Thank you
KushagraMathur
1CR15IS049
ISE 4A
BLOG 