Greedy Algorithm
Various computational problems necessitate the use of various techniques. Depending on the type of problem, a good programmer can employ any of these techniques. The following are some of the most widely used techniques:
- Divide and conquer
- Randomized algorithms
- Greedy algorithms
- Dynamic programming
Right now, I am gonna talk about the greedy algorithm.
What is a “Greedy algorithm”?
Any algorithm that follows the problem solving heuristic of making the locally optimal option at each point is known as a greedy algorithm. A greedy heuristic may yield locally optimal solutions that approximate a globally optimal solution in a reasonable amount of time in many problems, but it does not always produce an optimal solution.
How do you know which option is optimal?
Assume you have an objective function that needs to be optimized (either maximized or minimized) at some stage in the future. To ensure that the objective function is optimized, a greedy algorithm makes greedy choices at each step. The Greedy algorithm only has one chance to find the best solution, so it never goes back and reverses the decision.
Greedy algorithms have both benefits and drawbacks:
- It is relatively simple to devise a greedy algorithm (or even multiple greedy algorithms) for a given problem.
- It will be much easier to evaluate the run time of greedy algorithms than it will be for other techniques (like Divide and conquer). It’s unclear if the Divide and conquer strategy is fast or slow. This is because the size of the problem shrinks as the number of sub-problems grows with each step of recursion.
- The challenging part is that knowing correctness problems for greedy algorithms is far more difficult. Even if the algorithm is right, proving why it is correct is difficult. Proving the correctness of a greedy algorithm is more of an art than a science. It necessitates a great deal of imagination.
- Greedy algorithms often (but not always) struggle to find the globally optimal solution since they do not run through all of the data exhaustively. They can make premature commitments to such alternatives, preventing them from later deciding the best overall solution. If a greedy algorithm can be shown to yield the global optimum for a given problem class, it is often chosen over other optimization methods such as dynamic programming because it is faster.
How to create a Greedy Algorithm?
You have exactly T minutes to do some jobs, and you want to get the most out of it. You’re given an array of integers, each of which represents the time it takes for a job to finish. You want to figure out how many things you can get done with the amount of time you have.
This is a straightforward Greedy-algorithm problem. You must greedily pick the items that will take the least amount of time to complete in each iteration while retaining two variables: totalTime and numberOfThings.
First, you must:
- Sort the array in ascending order.
- Pick each to-do item one at a time.
- To totalTime, add the time it will take to complete the to-do list.
- Increment numberOfThings by one.
As long as the totalTime is less than or equal to T, keep doing this.
Let arr = {5, 2, 1,4,3} and T = 5
On sorting, arr = {1, 2, 3, 4, 5}
After the 1st iteration:
- totalTime = 1
- numberOfThings = 1
After the 2nd iteration:
- totalTime is 1 + 2 = 3
- numberOfThings = 2
after the 3rd iteration, currentTime is 3+3=6, which is greater than T. Therefore, the answer is 2.
Implementation :
#include <iostream>
#include <algorithm>
using namespace std;int arr[100];
int main()
{
int i, T, N, numberOfThings = 0, totalTime = 0;
cin >> N >> T;
for(i=0; i<N; ++i)
cin >> arr[i];
sort(arr, arr+ N);
for(i=0; i<N; ++i)
{
totalTime += arr[i];
if(totalTime > T)
break;
numberOfThings++;
}
cout << numberOfThings << endl;
return 0;
}
Where to use Greedy algorithms?
For a greedy algorithm to function, it must have these two components:
- It has optimal substructures. The best solution for the problem also includes the best solutions for the sub-problems.
- It has a greedy property i.e., proving its correctness is difficult. You can always arrive at an optimal solution if you make a decision that seems to be the best at the time and solve the remaining sub-problems later. You will never have to second-guess your previous decisions.
