So in today’s topic, I’m going to be explaining greedy algorithms. Now this is really meant to just be an introduction to this topic. So in this video, I will explain to you what a greedy algorithm is, how you can go about creating a greedy algorithm and then show you a few examples of it. But with that said, if you want to learn more and practice with greedy algorithms, what you can do is check out the sponsor of this video
What Are Greedy Algorithms ?
Now, before I do that, I will note that I do have very messy handwriting. So please, excuse me. I’ll try my best to make everything as neat as possible in this video with that said, what is a greedy algorithm? Well, a greeny algorithm is really an algorithm that makes a greedy choice. You can think of this as kind of an optimal choice at every single step in the solution or in the problem. Now, the greedy choice is defined by some rule, that rule could be select the largest number, select the smallest number, select the element that has a certain property, whatever you’re making some definitive choice, some greedy choice at every step in the algorithm. Now, greedy algorithms can be very complicated.
They can also be quite simple to give you an explanation or kind of an example of a greedy algorithm. Let me kind of introduce a problem to you right here. So let’s say for this problem, we’re given some array and this array is filled with integers. So I have three, four negative one to negative three and zero. And then maybe we’re given some integer, N we can say here that N is equal to four. Now what this problem is asking us to do is to find the N numbers in this array.
It equal be the largest sum. Now, if that’s the case, the greedy algorithm approach to solving this problem is to simply select the largest number at every single step until we’ve selected N numbers in this should hopefully solve the problem for us. So if we apply the greedy algorithm approach, we’re selecting the largest number at every step until we’ve hit four numbers. So what we do is we start by selecting four because this is the current largest number. So we select four.
Then we select three because four was already selected. So now we have three and four, then we select two. And then finally we select zero. And what will we get is 4, 3, 2. And one, which means that we have an answer of 10 says the largest sum that we can create by selecting four numbers. And this would actually be our answer here. We would return 4, 3, 2, and one. So that’s an example of a very, very simple greedy algorithm where all we did was select the largest number at each step. And we’ll that led us to the solution.
So I know the example I just showed you is relatively trivial, but it’s the best way that I can show you what a greedy algorithm is without getting into any super formal explanations. So as you saw there, a greedy algorithm is really just an algorithm that makes an optimal or greedy choice at every single step. And eventually all of those choices lead to an optimal solution at the end of the program.
Greedy Algorithm Properties
Now, before we get into some more advanced examples here, I’m going to give you two kind of formal definitions or formal properties of when you can actually use a greedy algorithm to solve a problem. So if the following two properties that I’m going to state are true, you can use a greedy algorithm and you’ll be able to solve the problem. So the first property is called the greedy choice property. And what this says is that a global optimal solution can be reached by choosing the optimal choice at each step. And then the second property that needs to be true as well is the optimal substructure property, which says a problem has an optimal substructure, if an optimal solution to the entire problem contains the optimal solutions to the sub-problems.
So to kind of break that down a little bit, what that means is every time you make a choice, you can kind of treat that as a sub problem. Now, an optimal substructure exists. If all of those sub problems allow you to solve the larger problem as a whole. So really it’s saying if all of the solutions to these sub-problems combined allow you to have a full, optimal solution to the entire problem, then you’re good. You can go ahead and use a greedy algorithm. So I’ll leave those definitions on the screen so that you can read them.
And I’ll give you one more kind of formal definition here before we get into another example. This says really algorithms work on problems for which it is true that at every step, there is a choice that is optimal for the problem up to that step. And after the last step, the algorithm produces the optimal solution of the complete problem. So that makes it seem a little bit more confusing than it really is. What I’m going to do now is move on to another example and show you how we apply a greedy algorithm to it. So in front of me, I have a very famous problem, which is known as the knapsack problem.
Fractional Knapsack Problem
Now, what I’m going to do is introduce a variation of this problem to you, and then explain how a greedy algorithm can be used to solve this. Then I’m going to go back to kind of the original problem and show you how the greedy algorithm fence. So let me introduce what this problem is. So in this problem, you have a, that has a specific capacity. In this case, the capacity is 20 funds. Now that denotes kind of the size in total of items that you can hold in the backpack. Some people call it weight, you can call it whatever you want, but that means that we can only store at most 25 kind of, you know, units of items in our backpack. And what our goal is, is to fill the backpack with as much value as possible without going over its capacity.
So we can see that each item has a size here and has a value. So if we’re looking at item zero, it has a size of 22, and it has a value of 19. We look at item one, we have a size of 10 and a value of nine. And so if we were to select say item one, that means that we would then be left with 15 units of capacity in our backpack. And we would have a total value of nine. So again, the goal is to maximize the value without going over the capacity, but you can be at the capacity. So you could use 25 units of space in the backpack.
So the question here is how do we use a greedy algorithm to solve this problem? And actually I need to introduce her to the variation of this problem, which is you can select a fractional amount of any of these items. So what that means is that let’s say we want to select item one, but we don’t have enough room for the entirety of item one. We can select half of item one. So if we were going to select half of item one, then what we would do is, you know, say 0.5 times 10, that’s how much weight we’re going to have four, half of item one, and then 0.5 times nine. That’s how much value we’re going to get. If we select fractional amount of item one, now you don’t have to just select half. You could select 99% of it. You could select 1% of it.
You could select 10% of it, whatever you want, you can select a fractional amount of an item. So my question is how do we use a greedy algorithm to solve this fractional backpack prompt? Well, the first thing that we should consider is can we solve this problem by just looking at one of these columns here? So just the value or just the size, can I select items that just have the largest value? Can I select items that have the small size, what is kind of the greedy approach? So what you see, what happens if we try to select items that have the smallest size first and see if that actually gives us an optimal solution. So at each step in our algorithm, we’re going to select the remaining item that has the smallest size, that’s kind of our greedy step.
And so the first item that we’re going to select here is going to be item three, because it has a size of seven. So when we do that, we see that our current size is going to be seven and our current value is going to be six. And then we can cross this off because we’ve used it. Okay. The next greedy step is we’re going to select the size of nine. So we select nine. That gives us a total size of 16. And then our value is now 15 because well, nine plus six is 15. Okay. And then we’re going to select our next item.
The next item has a size of 10. And when we select this item, we see that this is going to lead us to go over capacity to 26. So what we need to do is select a fractional amount of this item, which means, instead of selecting all 10, we’re going to select 90% of this, right? So we’ll select nine of 10, which means we are going to get now a capacity of 25. And then what’s 90% of nine. Well, let me just use the calculator to get that. I probably should have been able to solve that in my head with that. It’s going to give us 8.1 value, which means we’re going to have a total value of 23.1. Perfect. So there you go. We now have a total capacity of 25, a value of 23.1.
And that’s kind of the answer we got when we selected items that had the smallest size, that was the greedy choice that we made. So let me just kind of move this over to the side here. So we remember this value and now let’s try it in the other way. All right. So now we’re going to perform the greedy algorithm, but this time choosing the largest value instead of the smallest size. So if I’m selecting the largest value, that means I’m going to select items zero. So we have a size of 22 and a value of 19. Then I’m going to be choosing between item one and item two, because they have the same largest value. Since this has a smaller size item two, I’m going to select this one. And so that means that if I were to select the entire item, I would have a weight of 31.
Obviously I can’t do that because that goes over my capacity. And so instead I need to select 33% of this item. So that means that my capacity is going to go to 25, 30 3% of nine is clearly three same thing here. That means that I am going to get an additional to value here. And that is going to lead me to 22. So let’s take this and store this down here as well. So the two answers we got were 23.1 and 22. Now what we can say right now is, okay, well clearly the other approach selecting the smallest size worked better for this example, but is this actually the optimal answer are either of these, the optimal answer to this problem. And well, the answer to that is no, there’s actually a better way to solve this, still using a greedy approach, but it requires a little bit of thinking.
So the purpose of me showing you those two methods, there was the illustrate that in a lot of examples, you can use a greedy algorithm, but you have to make sure you’re really thinking about what your greedy criteria is, how you’re selecting the optimal choice at every single step. Now, for this problem here, you have to remember that we can select a fractional amount of all of these items. And so really what we should do is find the items that have the best value to size ratio, select the largest fractions of those items that we can, and then continue on throughout the algorithm. So I’ll show you what I mean by that, but let’s just have a look here. So what I’m going to do is make another column and I’m going to call this value over size.
Now, the point of this is that the items that have the largest value oversize ratio are the best items for me to select. So quite simply, if we’re looking at this right here, nine size gives me nine value. That means my value to size ratio is one. So for every extra capacity I add or remove, I guess from my backpack, I get one value. Whereas if we’re looking at say 22 and 19, I need to pull up my calculator for this. But 19 divided by 22 is 0.8636. If we’re looking at a nine and 10, we’re going to get 0.9. And if we’re looking at six and seven, then we’re going to get 0.857. So here we can see that the best item to select in terms of the value to size ratio is going to be item two. And then we’re going to have item one. And then it’s going to be item zero, followed by item three.
So now what our new greedy algorithm should do here, the correct greedy algorithm is that each step in our algorithm, we should select the item that has the highest value oversize ratio and take as much of that item as we possibly can. So in this case, we see that this is our best item. So we’re going to take all of item two. So I can just, I guess, write what our weight and our size is going to be over here. So that’s item two. We’re going to select all of that, then this guy’s done. So what’s the next one. Well, we want to select item one.
So we’re going to select all of item one, which means we’re going to get now a capacity of 19 and we’re going to have a value of 18. So this guy’s done now. And then this is slightly better than this. So we’re going to select as much of item zero as we possibly can. So we need to select kind of six size of item zero. So let me do some math here. So we’re going to select approximately 27% of items zero. So 27% times 19 gives us a value of 5.18, which means that we’re going to have here 23. If I can do this correctly, 23.18 like that, and then we’re going to have a capacity of 25. So we did actually end up with marginally more value by using this different greedy approach that I just showed you right here. Now, a lot of you might think that this is a calculation error.
This is not, there is actually slightly more value in doing the method that I just showed you here. So selecting a fraction of this specifically 27% of it now in a lot of other examples, you’ll see that this difference will be much larger, but the whole point of this was just to illustrate to you that you need to be very careful in what you actually use as your greedy criteria. It’s not as simple as just looking at one category. In this case, we combined the categories and intuitively this does make a lot of sense, right?
To select the highest fraction of items that we can, that have the largest value over size, right? Or value to size ratio. So that’s the example that I wanted to show you on how you can actually use a greedy algorithm to solve a problem. I’m not going to write the code for this. You can figure that out on your own. But now what I want to do is change the variation of this problem and show you how a greedy algorithm might actually fail. All right?
So I’ve cleared the screen. And now what I want to do is change the variation of this problem and show you how the greedy algorithm will fail when we change the problem just slightly. So now the problem is the exact same. You want to maximize the value without going over the capacity.
However, you can not select a fractional amount of an item. So if we try to perform the greedy alligator than we did in the last step, where we select the item that has the largest value to size ratio, you’re going to see that we quickly fail and we do not get the correct amount, or we do not get the largest value we possibly can. So let me prove it to you. This was the item that had the best us value to size ratio, second, best, third, best, and fourth best. So if we select this item, first, we get nine and nine, and then we select this item.
We get a total capacity of 19, and then we get a value of 18. And now we try to select the next item. And we see, we cannot select another item because there is no item that has a size small enough, uh, that we can fit in the bag with a capacity of 19 already being used. And so our value from the greedy algorithm approach is 18. So obviously this means that the greedy algorithm fails in this example and cannot deliver an optimal solution. And one of the reasons it can’t do that is because of the choice it makes in the current step actually affects what choices it’s going to have to make in the future because we have this capacity constraint. And so we really would be better off using something like dynamic programming here to solve this problem rather than a greedy algorithm.
In fact, a greedy algorithm just will not give us the correct result unless we’re lucky. And the greedy algorithm choices end up lining up with what the actual optimal value should be. So with that, I think I’m going to end the video here. Hopefully this gave you a quick introduction to what greedy algorithms are.