If we are dealing with the Greedy way, we should know what the Greedy approach is. The question says it – “Greedy”. Greedy takes the maximum value first to
give you the optimal solution.
Greedy Algorithm for an optimization problem always makes the choice, which looks
best at the moment and adds it to the current sub-solution. Greedy algorithms do not always yield an optimal solution, but when they do, they are usually the
simplest and most efficient algorithm available.
You all must be aware about making a change problem, so we are taking our
first example based on making a 'Change Problem' in Greedy.
To construct the solution in an optimal way, the Greedy algorithm consists of
four (4) functions, which are as follows.
- A function that checks whether a chosen set of items provides a solution or not.
- A function that checks the feasibility of a set.
- The selection function tells which of the candidates is the most promising.
- An objective function, which does not appear explicitly, gives the value of a solution.
Use a Greedy approach, give the least amount of coin for 41, using a coin set {1, 5, 10, 25, and 50}?
Here, we have to make 41, using a coin set. We cannot use a coin other than the coin set and yes the coins are infinite in value ( as we take this as an ideal condition).
41 -- > {1, 5, 10, 25, and 50}
As we know, Greedy takes the maximum next value first. It is inferred from it that Greedy works in Top- down fashion.
For 50 - We can select the highest value as 50, but we cannot take it as we want to make 41, and 50 > 41, so we will go to the next value to check.
For 25 – We can see 25 < 41, so we can proceed with our first step. From the table, mentioned below.
We had used 25. 41- 25 = 16. Now, go to the next coin in the set, which is lower than 16 as we have to find the optimality for 16. Thus, after 25, there is 10 that is (10 < 16) smaller than 16 definitely we can use it. So 16- 10 = 6.
In this fashion, if you will hit a point, where you get “0” as the remaining coins, in that case, whatever coins had been used is your optimal solution for the problem mentioned above.
| SNo |
Coins we take from Coin Set |
Remaining Coins |
Coin we had used |
| 1 |
41-25 |
16 |
25 |
| 2 |
16-10 |
6 |
25,10 |
| 3 |
6-5 |
1 |
25,10,5 |
| 4 |
1-1 |
0 |
25,10,5,1 |
Thus, for 41 -- > we had used {25, 10, 5, 1} and this is your optimal solution.
Now, it is not necessary that it always gives you the optimal solution, which means Greedy Fails too in some awkward conditions. Let’s suppose 'Making a Change' is the same as 41, but the coin set is now {4, 10, and 25}.
'Make a Change' for 41, using coin set- {4, 10, and 25}
| SNo |
Coins we take from Coin Set |
Remaining Coins |
Coin we had used |
| 1 |
41 -25 |
16 |
25 |
| 2 |
16-10 |
6 |
25, 10 |
| 3 |
6-4 |
2 |
25, 10, 4 |
| 4 |
2 - ? |
Here it Fails |
|
As you can see in the last part, there is no coin in the set, which gives the optimality. Thus, we can say Greedy fails here.
To make solution for the problem, mentioned above, we can proceed in a way, mentioned below.
| SNo |
Coins we take from Coin Set |
Remaining Coins |
Coin we had used |
| 1 |
41 -25 |
16 |
25 |
| 2 |
16-4 |
12 |
25, 4 |
| 3 |
12-4 |
8 |
25, 4, 4 |
| 4 |
8 - 4 |
4 |
25, 4, 4, 4 |
| 5 |
4-4 |
0 |
25, 4, 4, 4, 4 |
Here, optimal solution for 41-- > {25, 4, 4, 4, 4} and I think it is better than failing a Greedy Approach. Make a comment for other options, where Greedy Fails!!
Hope you like it. Thank you for reading.