What are greedy algorithms?
Greedy Algorithms are optimization algorithms that are simple, easy to implement, and intuitive. Greedy algorithms work on the premise that if we keep making the locally optimal option in each subproblem, we can eventually arrive at the global optimal solution for the whole problem.
Greedy Algorithms’ Properties
Greedy Algorithms can be used to solve problems if two conditions are met:
· Greedy Choice Property: By selecting local optimums, a global optimum can be found.
· Substructure Property: A problem has optimal substructure property if the problem’s optimal solution can be derived from the subproblems’ optimal solutions.
To understand what a greedy approach lets take a classical problem fractional knapsack
Imagine you’re planning a long hike. It might take a few days or a few weeks, but you have no idea how long it will take. So, in order to be safe, you should bring enough food with you. You also have a knapsack that can carry up to 15 kilograms of food. And you’ve already purchased some cheese, ham, nuts, and possibly other food products. You’ll want to cram them all into the knapsack to get the most calories out of them. You should, of course, chop the cheese. The ham can be chopped. Only a few of the nuts are available for selection. Then cram everything into your knapsack.
We must first reformulate this maximisation problem in mathematical terms in order to solve it. Then it becomes a classic fractional knapsack problem, which goes something like this. We have n objects with W1 through Wn weights and V1 through Vn values.
And a bag of capacity W. And we want to get the most value of the fractions of things that fit into this bag.
In this case, weights are the energy values of the food items you’ve purchased, and values are the weights in real life.
So, as an example, the item’s value will be expressed in dollars, while the weight will be expressed solely in numbers. The first item, for example, is worth $20 and weighs 4, the second is worth $18 and weighs 3, and the third is worth $14 and weighs 2. And we have a knapsack of capacity 7. There are a few ways with which we can fill this knapsack.
Put the entire first item and the entire second item in the knapsack, for example. The cumulative value is then equal to the sum of the first and second item’s values, which is $38.
That is something we should work on. For example, for a total of $40, take the entire first item, the entire third item, and just one-third of the second item.
We can save even more money if we take the entire third item, the entire second item, and only half of the first item, for a total of $42. In fact, it turns out that this is the best solutuion.
So now we want to create a greedy algorithm to solve this maximisation problem, and we need to make a safe move and get some greedy options. And in order to do so, we must consider the value per unit of weight. For example, the first item’s value per unit of weight is $5, the second item’s value is $6, and the third item’s value is $7. So, if the first item is the most valued, the third item has the highest per-unit value. Of course, it’s natural to assume that we should start with the items with the highest per-unit value.
In fact, the safest move is to try to fit the item with the highest value per unit first. There’s also a lemma that says there’s always some optimal solution to our problem that uses as much of an item with the highest value per unit of weight as possible. What exactly do we mean when we say “as much as possible”? So, either use the entire item if it fits in the knapsack, or if the knapsack’s capacity is less than the amount of this item we have, fill the knapsack entirely with this item.
Let’s show that this is a sound decision.
We’ll demonstrate using this example. So, let’s say we have an optimal solution, and let’s say we don’t use as much as possible of the best item with the highest value per unit of weight in this optimal solution. Then take one of the items we used in this solution and divide its usage into two parts: one part equal to how much of the best item we have, and the other part equal to everything else. Then we will use the best item to replace the first part. So, in this case, we replace half of the first item with the second item.
Of course, the total value would rise in this section because the best item’s value per unit of weight is higher than the item currently in use. This will also work in the general case. So, either we’ll be able to replace a portion of an item that is already being used by the entire best item, or we’ll be able to replace the entire item that is already being used by a portion of the best item. In any case, if we can make such a substitution, the total value will increase, since the best item simply has a higher value per unit of weight, so we will have more value per unit of weight. As a result, we now have a greedy algorithm to solve our problem.
When the knapsack is still empty, we’ll make a hasty decision. We’ll go with item number I because it has the greatest Vi value over Wi, which is the weight value per unit. Then, if this item fits entirely inside the knapsack, place it there. Otherwise, take enough of this item to entirely fill the knapsack if there are only a few spaces left. Then, at the end, we’ll return the total value of the items we took, as well as how much of each item we took.
But How do we code Greedily??
Knapsack is a function that we have here. It begins by initialising the total value and the array A with 0 values, and then repeating the iterations for n times, as shown on the Image. If the knapsack is already complete, we will have 0 in the variable W because we have the total capacity of the knapsack in the variable W at the start, so each time we add anything in the knapsack, we will update W and reduce it by the amount of weight we have already put in. As a result, when the knapsack is complete, W equals 0. If W became 0, it means that we should just return the total value and the amounts of the items that we took.
Otherwise, the best option should be chosen. The better item is the one that is still left so that Wi is greater than 0, and it is the item with the highest value per weight, that is, the one that maximizes Vi over Wi.
When we’ve chosen the I we’ll figure out how much it’ll take; it’ll be the entire Wi, or the entire item if it fits in the knapsack. Otherwise, if the knapsack’s capacity is already low, we simply fill it to the top. As a result, A is the smallest Wi and the largest W.
We simply update all the variables after selecting the amount. As a result, we reduce Wi by a, since we already have an of this item. We also added the value A to the quantity A of I which corresponds to the item number i. We’ll also reduce the remaining capacity because we’ve already reduced it by A. By making it in position A of item i.
Also, by multiplying A by Vi and dividing by Wi, we can increase the value V. What is the reason for this? We got A units of item number I because we took A units of item number I and one unit equals vi over Wi. So, if you multiply A by vi and divide by Wi, you get the cumulative value of these objects.
We’ll return the total value and the sums in the array after n iterations, or less if the knapsack is complete until we finish all n iterations.
When you have a problem, the general approach is to come up with some greedy options, and then show that some of them are actually safe moves. And if you’ve shown that this is a safe move, you’ve effectively solved your problem. Then you’ve reduced your problem to something. Then you must determine whether or not this something is a subproblem.
