Greedy Algorithms - Algorithms & Data Structures #8

Key Takeaways

[Music] what is going on guys welcome back to the algorithms and data structures tutorial series in today's video we're going to talk about greedy algorithms and greedy algorithms are essentially just a category of algorithms that have certain characteristics and in today's video we're going to briefly mention them we're not going to talk about them too much in detail i just want you to have heard of them which is why i'm making this video at this point in the series i want you to know about greedy algorithms what they are what they look like we're going to look at an example today so that you can see how greedy algorithms look so that you can recognize them in future videos we're going to use some of them in the future and i also want you to see that sometimes they're very efficient or you should use them in some cases and sometimes they don't produce optimal results so let's get right into it so in order to explain greedy algorithms i'm going to use a very simple example uh let's say we have three types of coins so we have one cent we have five cents and we have 10 cents uh these are the types of coins that we can use and we have an unlimited amount of those uh so now the question is if i'm given a certain amount of cents for example 47 cents how can i find the optimal solution when the goal is to get to that amount to give the person this amount of sense with the least amount of coins possible with the smallest amount of coins possible so of course if someone says i want 47 cents and i have an unlimited amount of all these coins i can just go ahead and say okay i'll give you one cent 47 times but then i end up with 47 coins which is not an optimal result and the question is can we find an optimal solution now to this problem the optimal solution would be 10 cents times 4 five cents times one and one cent times two so we end up with seven coins and a total of 47 cents is a very simple solution optimal solution and the question now is not just how can you solve this for a particular number for example 127 would be another number that we can choose uh the question is can you find an algorithm and we don't need to write down the pseudocode just by logical thinking can you find an algorithm that always gives you the optimal solution and it's not obvious that any algorithm that seems intuitive will work here so now what we did in the first example here with 47 cents for example is we just looked at okay what is the largest coin here 10 cents okay how many times can i use 10 cents in order to get to 47 okay i can use it four times so i end up with seven cents left and then i can use the five cents then i have two cents left so i can just go ahead one cent times two okay now what we're doing here is applying a so-called greedy algorithm and a greedy algorithm is defined by always picking the solution the local solution that seems the most beneficial right now so you're not looking long-term you're thinking okay what decreases the value of the um of the price here so we we have 47 cents decreasing 47 cents the most with one step is is done by subtracting 10 cents right it doesn't have to be the case that subtracting 10 cents is necessarily the best solution long term maybe if i subtract 10 cents now it's going to be a problem later on now i can spoil the surprise for you in this case in this constellation the greedy algorithm will always give us the best result so uh actually doing this and picking the largest possible number will give us the the best results in this case but this is what a greedy algorithm does it looks at the value 51 for example and asks okay how can i decrease this value the most with my next step it doesn't ask the question of how can i decrease it in in the long run uh with the least amount of coins possible it looks okay which is the next value that i can choose to decrease this number the most and the answer is the largest coin and we do this as long as the largest coin still fits into the value and then we choose the other coins however it is not always necessarily the case that a greedy algorithm gives you the best result possible for example let's pick a different uh set of coins so we have one cent 5 cents and 10 cents again but then we can also add 20 cents and 25 cents now notice i'm not picking any prime numbers or something i'm not picking any uh super crazy numbers here these are ordinary numbers and the goal now is to uh find optimal solutions now of course if i have something like 30 cents i can go ahead and say okay 25 cents plus 5 cents is 30 cents so i have two coins as the optimal solution so sometimes it still works but uh not necessarily every time for example let's look at 40 cents and 40 cents is an example where this would not work because the greedy algorithm asks what is the coin that i can use to decrease this value the most right now the greedy algorithm is interested in the best solution locally we want to decrease the value to zero okay the best solution to do that right now as far as i can see is subtracting 25 cents so okay what we do is we end up with 15 cents then i go ahead subtract 10 cents end up with five cents and then we go ahead and subtract the five cents and we end up with zero since using three coins however this is not the optimal solution because the optimal solution is not a greedy solution the optimal solution is just picking 20 cents two times two coins and we still end up with 40 cents so this is as you can see a proof that greedy algorithms are not always especially not in general but also not for this example where sometimes in some constellation a greedy algorithm always gives you the optimal result if you only use these three coins here a greedy algorithm will always give you the optimal result however sometimes in different constellations it's not going to be the case so you have to be careful and i just want you to know what greedy algorithms are that sometimes they work sometimes they don't work and now you should know about this and we'll see a lot of greedy algorithms in the future so that's it for today's video thanks for watching i hope you enjoyed it was a very short video but i just wanted to mention greedy algorithms in a separate video here because it is an important topic you should know about them i just wanted to have it mentioned here i hope you enjoyed it in the future videos we're going to talk more about uh sorting algorithms now we're going to start analyzing them we're going to talk about divide and conquer sorting algorithms runtime complexities of bubble sword insertion sword selection sword merge sword and so on we're going to analyze all of them and uh yeah that's it for today's video i hope you enjoyed it leave a like and leave a comment in the comment section down below if you enjoyed this video subscribe to this channel to see more future videos for free and thanks for watching see you next video and bye [Music] you