All language subtitles for 26 - Introduction to Greedy Algorithms English

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.