Original subtitles

‫High in this video I'm going to introduce greedy algorithms.

‫How they work on a high level.

‫Give some examples on how they work.

‫And then also some scenarios to show you when a greedy algorithm is not a good idea.

‫And so essentially how a greedy algorithm works is it takes the highest value first.

‫And so here on the left hand side I have some American currency in coin values of 25 cents ten cents

‫five cents and a penny.

‫If you're watching from the U.S. you know that's a quarter a dime a nickel and Penny one equals one

‫cent on the right hand side.

‫I have a made up currency that has values of 1 3 and 4 and I'm going to show you how a greedy algorithm

‫can be a great thing to implement in order to figure out a problem efficiently.

‫And then also give a situation where it wouldn't be a good idea.

‫And so in the first scenario I'm going to have a goal of getting 31 cents and I want to use the fewest

‫number of coins possible and in order to do that on the left hand side here I can take a quarter

‫plus a nickel

‫Plus a penny and that's going to give me 31 cents.

‫And in this case by going to the highest value first which is what a greedy greedy algorithm is always

‫going to do.

‫So I went to the quarter first and that was the best way of doing it because this only took three coins

‫some other ways of doing it would have been to use

‫three dimes and one penny which would have given us still 31 cents but it would have required four coins.

‫And so that would not have been the optimal solution.

‫Now there are times even in this scenario where this would not be the best way of going about it and

‫the way to do that would be to say that we're not allowed to use nickels in the case where we're not

‫allowed to use nickels.

‫We'd have to use a quarter and then we'd have to use six pennies in order to get our goal of 31.

‫And this would equal seven coins and you can see with the example above we were able to get to 31 cents

‫using only four coins and no nickels.

‫So a very important thing in understanding greedy algorithms are making one work is that you know the

‫the data that you're using because it will not work in a lot of different cases.

‫I'm going to go in the right hand side and show you another case where this would not work and where

‫this case would not work is where we're trying to get to the value 6.

‫And so this is a made up currency so we don't have any threes or fours.

‫However I wanted to give another example on when a greedy algorithm are you know taking the largest

‫value would not be a good idea.

‫If we want to use the smallest number of coins and we took a greedy algorithm to get to the value of

‫six we would take one for and then we would have to take two ones in order to get to six.

‫Now this takes three coins.

‫However the better choice would have been to just take two of this coin of three value which would equal

‫six.

‫And in this case we'd only use two coins and this would have been the optimal solution.

‫So hopefully that gives you a good idea and how greedy algorithms work at least on a very high level.

‫Well we'll work on actually implementing some of these and seeing some real world examples on how these

‫could work.

‫But the main principles that you want to understand is a greedy algorithm always takes the highest value

‫and then it essentially selects other items that are secondary in value until it reaches its goal and

‫it will work in some cases.

‫However you do have to know your data.

‫You need to know your values to ensure that it actually is the optimal solution.

‫So as always please let me know if you have any questions in the comments and I'll see you in the next

‫video.