OK, so now that we talked a little bit about dynamic programming, but preceding that we talked about
both dynamic programming and the greedy method.
We are going to now look at an introductory, greedy method problem, so I'm going to kind of be intertwining
these two things.
The dynamic programming and greedy method just so we can see the goods and the bads of each and when
to use them, what they use for and how sometimes one may prevail over the other.
So let's get started.
This is going to be the first problem for the greedy method, and it's going to be the optimal change
problem.
So let's see what that is.
So here is a problem statement for us.
Let's say we're given an array or vector of money to nominations, so it's like bills or coins.
Specifically, I'm going to be referring to coins and examples in this, but it could be there or so.
Also, let's say they are sorted in ascending order.
So this is a pretty sorted vector or array.
We are also giving a value see for change.
So the question is, how do we find the combination of the minimum possible number of coins, those
coins, but missing coins to create the change?
So basically, what we're trying to see is the optimal combination of these denominations.
If we're meeting a specific amount of change and we're representing that with see?
So let's visualize the problem with an example.
So here we have denominations.
So one, five, 10, 25, 50 and then we say, OK, we need to make 56 change.
So you could say like 56 cents, whatever, but we just need 56, and we need to make that out of these
denominations in the fewest coins possible.
So how would you make 56 and change?
Well, normally what you would do if you're thinking about just your daily life, you probably would
see, OK, I'm just going to start off with the biggest thing I have that is less than what they're
asking for, and I'm just going to make change and kind of go down and be totally right with that.
As far as what we're about to do.
So we start off with 50 because they asked for 56 and change, and we do have a 50 and here, so you
might as well give them that, then we can do a five after that and then we can do a one.
So that's probably what you would do is you'd say, OK, I have a 50 cent piece if we're talking just
like U.S. currency, I have a 50 cent piece after they give them that.
I only need six more, so I'm going to give them a nickel five and then I'm going to give them a penny
to complete it there.
So that would equal 56.
So how does the grilling method relate to this?
Well, you might have noticed that what we did was we just started it the largest number, which is
the right mast in the array.
And then we worked our way down, choosing the biggest values as we went until we satisfy the requirement,
which was 56.
So this is straight up just the definition of the greedy method.
We're always actively choosing the largest possible value.
So here we have our denominations again.
You see what we did.
We said, Hey, we need 56.
So oh, I have 50 cent, why don't I use that?
And this isn't just what you have on hand.
These are the down denominations.
So technically, we're assuming there could be an infinite amount of each one of these.
Imagine just a cash register that's filled with plenty of these denominations of coins that you'll never
run out of.
So I use a 50 and then basically at that point, you know, I only need six left, so I'm not going
to use these because I can't.
That would be given too much change.
So the next thing I can use is a five.
The next biggest thing.
And then I use the one after that because I can't use anything greater than the one.
So let's think about how we did this in our daily lives and come up with an algorithm that's more specific,
so we have the general idea that we're kind of starting over here and working our way down.
So step one, find the largest coin, it doesn't exceed the value of the change needed, and we're representing
change needed as C C is 56.
So we do that, we subtract that coin value from sea.
So we found 50 and that was the largest coin that didn't exceed the value.
It's less than 56 and we subtracted that from it.
So then we just have six.
And then we just keep doing step one and two until there's no more change needed, which is when C is
equal to zero.
So what we did when we just had six left is we found the largest coin that didn't exceed the value of
the change needed, which is the current change.
We only have six left.
So the largest coin that doesn't exceed their value is five, so then we subtracted five, and that
gave us one and then the largest coin it didn't exceed one is one itself here.
So we subtracted that, and then we got to the point where C is now a Sierra, we've given on the change,
so we're done.
So now let's start out with a function definition here on how we would turn this into code.
And let's break down our algorithm into some actual C++ code.
So here I am saying that I'm going to return the vector that contains the answer of all of the denominations.
So you might also be asked to just return the like.
Let's say you're being asked for a function that does what the problem statement describes.
Sometimes you might just be asked to return the minimum number of coins.
So it's like the count in which our case, it would just be the size of the vector because what we're
doing is trying to record the actual combination of the coins that we used for change and store that
in a vector.
So that's what we're solving in this problem.
But if they also wanted to know how many coins were used, what was the minimum amount of coins, then
we kind of already solved that with the fact that we have them in the vector so we can just reference
the vector size to get that answer as well.
So let's continue on here.
I've defined the optimal change function.
We get past our vector of denominations here, and then we also get past an integer see, which is the
change that we need to make from that denominations.
So first thing we're going to do is just make an empty vector to store our optimal combination of denominations,
and that's just being called solution here.
So what is the next thing we need to do?
Well, we need to move through our denominations starting the largest right, the rightmost, so we
can use a for loop for that where we start at the end.
This is just range based, but we're starting at the far right.
So that's denominate size minus one.
That's the last item.
And then we're going to the left with the R minus minus.
As long as I is greater than or equal to zero because so.
We're just moving through our denominations kind of like we were when we were just kind of doing our
normal algorithm there in the previous slides.
So we keep using the largest coin that doesn't exceed the value of the change needed, and that's like
the current change needed.
So Sea Eagles current change needed.
So this is while we can just use a while loop, and this is because we might want to use multiple of
one denomination.
So you notice that we're at a specific denomination, didn't I?
So let's say that was like 10 or something.
Well, we you might think, oh, we can just put in for something, but maybe it's optimal to use multiple
dimes or something like that.
So as long as it is the largest thing that we can keep using.
We're going to keep using it.
So this enables us to use multiple of the same type of denomination.
So I'll see greater than or equal to domination.
We're going to subtract the coin value from see like we just talked about in the previous slides.
So let's just see, we'll see minus two nominations.
That's us taking the coin away from our current change needed.
And then we're going to add that denomination to our solution.
So we're going to push it back to the solution factor because that's one of the coins that we used to
since we already subtracted it from our change needed.
And that's really all we do, we go through our vector.
So think back to the previous slides.
We went through our vector, we started on the right right here, and then we just moved to the left
and we're just this is already pretty sorted.
So what we're trying to do is just use the biggest value possible.
Is this greater than the current change that we still need to give?
If not, then let's use it if it is greater than we just keep moving through the loop.
So that's what the for loop is.
And then the while loop here was just us using multiple of the double now denomination if we need to
like or was talking about.
So we push that back and that's really all we need to do.
And so then we can just return our solution.
So this would be some awful example code right here, and you can write this out and tested if you like.
It just prototypes, the function we were talking about here is the same function here in just actual
C++ code in a file.
And then here's just a main function that uses our example with the denomination's.
So it just initialize this that on line 20.
And then we just have this loop that's printing out what our answer was.
So we're looping over the actual items inside of what was returned by the optimal change function.
And we're just pointing that out with some spaces, so you can run this, and it should give the proper
example, which I believe was if we're using 56, that was just 50 and then five and then one.
So pretty cool.
It's a nice algorithm, but unfortunately there is a problem.
So what if the denominations vector or array was something like this?
One eight nine 14?
You might be saying, well, that doesn't make sense.
Like what type of money is like that?
Well, we want something that can be used for any type of situation.
This problem could be applicable in more ways than just going over popular known currencies.
So let's just say that we're required to do it for any type of theoretical hypothetical denominations
that could be created in a currency.
So if we have one, eight, nine and 14 and they say, OK, well, I want you to come up with 17 change
from these denominations, what is the minimum number of coins that you can use to make change?
So I want you to maybe pause the video right now and see if you can figure that out.
Well, so if you looked over that you probably said, well, the answer is two coins we can use and
nine and eight.
And that gives us 17.
Is this what our greedy algorithm would choose, though?
Think about it, so just pause the video if you need to again and try and go through this the nominations
and see what our greedy algorithm would do.
So actually, unfortunately, the answer is no.
Our greedy algorithm would choose the combination 14 plus one plus one plus one equals 17, which is
four coins instead of two coins and therefore is served.
Optimal is not an optimal solution.
So and you can test this out as well, you can just basically go in and replace it in that code in the
previous slide, you can replace the vector with this hard coded.
Section right here and then also replace the seat that's been passed to the function was 17 instead
of 56, and you should see that this gets printed out right here.
So what are we going to do now?
We just thought we had this cool algorithm, and now we realize that it doesn't necessarily always produce
the optimal solution we were hoping for.
So the good news is there's a fix we can actually use dynamic programming, which we've already talked
about a bit to solve this.
And so since this lecture is taken a little bit of time and I don't want to combine too much in one,
I'm going to go ahead and go over that in the next lecture, so I will see you in the next lecture.