>> Let's get greedy.
>> Let's get greedy.

In greedy, our job is to play the role of a greedy cashier.
In greedy, our job is to play the role of a greedy cashier.

The user will tell us how much change we owe them,
The user will tell us how much change we owe them,

and then our job is to calculate the minimum number of coins
and then our job is to calculate the minimum number of coins

that we can use to make that amount of change.
that we can use to make that amount of change.

>> Let's start with an example.
>> Let's start with an example.

Say the user requires $0.32 back.
Say the user requires $0.32 back.

We could do this by giving them 32 pennies, one cent each.
We could do this by giving them 32 pennies, one cent each.

Or I could also use five coins-- by giving them three dimes, $0.10 each,
Or I could also use five coins-- by giving them three dimes, $0.10 each,

and two pennies, $0.02 each.
and two pennies, $0.02 each.

But could we use even fewer coins to make that?
But could we use even fewer coins to make that?

>> The whole tactic in greedy-- to be a greedy cashier--
>> The whole tactic in greedy-- to be a greedy cashier--

is to use the largest coin possible.
is to use the largest coin possible.

So whenever we have quarters we'll use them.
So whenever we have quarters we'll use them.

And then once those run out, we'll use dimes, $0.10 each.
And then once those run out, we'll use dimes, $0.10 each.

Then nickels, 5 cents each, and then down to pennies, one cent each.
Then nickels, 5 cents each, and then down to pennies, one cent each.

By using the largest coin possible whenever we can,
By using the largest coin possible whenever we can,

we ensure that we use the fewest number of coins possible to make the change.
we ensure that we use the fewest number of coins possible to make the change.

>> So let's walk this through.
>> So let's walk this through.

The user needs $0.32.
The user needs $0.32.

So we ask ourselves, can we use a quarter?
So we ask ourselves, can we use a quarter?

Well, yes we can.
Well, yes we can.

So now we only know them $0.07, and we used one coin.
So now we only know them $0.07, and we used one coin.

>> Can we use another quarter?
>> Can we use another quarter?

Well, no.
Well, no.

$0.07 is less than $0.25, so we proceed to the next largest coin available.
$0.07 is less than $0.25, so we proceed to the next largest coin available.

Dimes are $0.10, and again, we can't use dimes.
Dimes are $0.10, and again, we can't use dimes.

Because dimes are worth $0.10, which is more than the amount of change owed.
Because dimes are worth $0.10, which is more than the amount of change owed.

>> We go to nickels.
>> We go to nickels.

And, yes indeed, $0.05 is less than $0.10-- so we can use a nickel.
And, yes indeed, $0.05 is less than $0.10-- so we can use a nickel.

So now we only owe the user $0.02, and we've so far used two coins.
So now we only owe the user $0.02, and we've so far used two coins.

We can't use another nickel.
We can't use another nickel.

So then we proceed to the last coin at our disposal, which are the pennies.
So then we proceed to the last coin at our disposal, which are the pennies.

>> And can we use penny?
>> And can we use penny?

Well, yes-- and we end up using two pennies for a total of four coins.
Well, yes-- and we end up using two pennies for a total of four coins.

>> Once you're finished, the program will look like this.
>> Once you're finished, the program will look like this.

Once the user runs the greedy program, they'll
Once the user runs the greedy program, they'll

be prompted to give the amount of change in dollars that they're owed.
be prompted to give the amount of change in dollars that they're owed.

And then your program will output the minimum amount of coins
And then your program will output the minimum amount of coins

that the greedy cashier would use to make that amount of change.
that the greedy cashier would use to make that amount of change.

>> So now let's break this down into our subtasks.
>> So now let's break this down into our subtasks.

First we're going to prompt our user for an amount of change.
First we're going to prompt our user for an amount of change.

And, as with any user input, we want to make sure that we validate that input
And, as with any user input, we want to make sure that we validate that input

and ensure that we can use that input for the rest of our program.
and ensure that we can use that input for the rest of our program.

Then we're going to always use the largest point possible
Then we're going to always use the largest point possible

and keep track of the coins used.
and keep track of the coins used.

And finally, print the final number of coins that we used.
And finally, print the final number of coins that we used.

>> So let's talk about prompting.
>> So let's talk about prompting.

The amount must make cents, and this is in dollars.
The amount must make cents, and this is in dollars.

And so for dollars, we're going to use the float variable type.
And so for dollars, we're going to use the float variable type.

Now whenever you ask a user for input, you want to make sure that it's valid.
Now whenever you ask a user for input, you want to make sure that it's valid.

And so here we like to take advantage of the do-while loop construct.
And so here we like to take advantage of the do-while loop construct.

>> A do-while loop will execute the body of the loop at least once.
>> A do-while loop will execute the body of the loop at least once.

So this comes in handy.
So this comes in handy.

We know that we need to prompt the user at least once for a float.
We know that we need to prompt the user at least once for a float.

Now if that float is valid.
Now if that float is valid.

That's great.
That's great.

We move on.
We move on.

But if not, the loop will ensure that we get a proper float
But if not, the loop will ensure that we get a proper float

by repeating continuously until the user gives us a valid value.
by repeating continuously until the user gives us a valid value.

>> Now for the do-while loop condition, we need
>> Now for the do-while loop condition, we need

to consider what it means to have an invalid float.
to consider what it means to have an invalid float.

So for the context of this problem, probably
So for the context of this problem, probably

it makes sense just to accept positive values.
it makes sense just to accept positive values.

>> So moving on-- we've obtained a value in dollars from the user.
>> So moving on-- we've obtained a value in dollars from the user.

But we're dealing with coins, which are entirely in cents.
But we're dealing with coins, which are entirely in cents.

$1 is equivalent to 100 cents.
$1 is equivalent to 100 cents.

So a good thing to do is to convert those values into cents.
So a good thing to do is to convert those values into cents.

>> Now when converting from a float to an integer, so dollars to cents,
>> Now when converting from a float to an integer, so dollars to cents,

we want to make sure that we're careful about floating-point imprecision.
we want to make sure that we're careful about floating-point imprecision.

So that means that-- say my dollar value-- my float
So that means that-- say my dollar value-- my float

value-- was an even $2, there still may be some stray numbers in there.
value-- was an even $2, there still may be some stray numbers in there.

So we want to make sure that not only do we multiply by 100 to get the cents,
So we want to make sure that not only do we multiply by 100 to get the cents,

but we also round it off.
but we also round it off.

>> So now we have the amount of change owed to the user.
>> So now we have the amount of change owed to the user.

We originally obtained it in dollars, and now we've converted it to cents.
We originally obtained it in dollars, and now we've converted it to cents.

So now we can proceed with the heart of the greedy algorithm, which is always
So now we can proceed with the heart of the greedy algorithm, which is always

using the largest coin possible.
using the largest coin possible.

While we're doing this, it's essential that we also
While we're doing this, it's essential that we also

keep track of how many coins are going to be returned to the user
keep track of how many coins are going to be returned to the user

as well as the remaining change owed to the user.
as well as the remaining change owed to the user.

>> The program will look something like this.
>> The program will look something like this.

After you get the amount of dollars and convert that to cents,
After you get the amount of dollars and convert that to cents,

then you'll enter a loop.
then you'll enter a loop.

While quarters can be used-- that is to say
While quarters can be used-- that is to say

while the amount of change owed to the user is greater than or equal to $0.25,
while the amount of change owed to the user is greater than or equal to $0.25,

you'll use a quarter.
you'll use a quarter.

>> Now what does using a quarter entail?
>> Now what does using a quarter entail?

Well, one-- you'll increase the coin count to be returned to the user.
Well, one-- you'll increase the coin count to be returned to the user.

And second you'll decrease the current amount of change owed back to the user
And second you'll decrease the current amount of change owed back to the user

by $0.25.
by $0.25.

>> After repeating that until quarters can no longer be used,
>> After repeating that until quarters can no longer be used,

proceed to the next largest coin-- in this case dimes, $0.10.
proceed to the next largest coin-- in this case dimes, $0.10.

So you'll enter that loop until you can no longer use dimes.
So you'll enter that loop until you can no longer use dimes.

Then proceed to the next largest coin, nickels.
Then proceed to the next largest coin, nickels.

After nickels can no longer be used, use the remaining amount in pennies.
After nickels can no longer be used, use the remaining amount in pennies.

And finally, print the number of coins used.
And finally, print the number of coins used.

>> Another way that you can approach the greedy problem
>> Another way that you can approach the greedy problem

is to use the modulo approach.
is to use the modulo approach.

Modulo is an operator that returns the remainder
Modulo is an operator that returns the remainder

of the division between two numbers.
of the division between two numbers.

Say I had 50 mod 5.
Say I had 50 mod 5.

Well, 5 is a factor of 50, so the remainder will be 0.
Well, 5 is a factor of 50, so the remainder will be 0.

50 mod 10-- well, 10 is also a factor of 50, so the remainder is also 0.
50 mod 10-- well, 10 is also a factor of 50, so the remainder is also 0.

50 mod 50-- well, any number mod itself isn't going to have any remainder.
50 mod 50-- well, any number mod itself isn't going to have any remainder.

>> What about 50 mod 49?
>> What about 50 mod 49?

Well, 49 only goes into 50 once.
Well, 49 only goes into 50 once.

So the remainder is going to be 1.
So the remainder is going to be 1.

53 mod 50 is going to give you a remainder of 3.
53 mod 50 is going to give you a remainder of 3.

>> So how can we use modulo and perhaps some division
>> So how can we use modulo and perhaps some division

to implement our greedy algorithm?
to implement our greedy algorithm?

Well, we still want to stay true to the heart of the greedy algorithm-- that
Well, we still want to stay true to the heart of the greedy algorithm-- that

is using the largest coin possible.
is using the largest coin possible.

>> So let's ask ourselves if we can use any quarters to return $0.32 to the user.
>> So let's ask ourselves if we can use any quarters to return $0.32 to the user.

Well, 32 mod 25 gives us a remainder of $0.07.
Well, 32 mod 25 gives us a remainder of $0.07.

So that tells us that we can definitely use one quarter with $0.07 remaining.
So that tells us that we can definitely use one quarter with $0.07 remaining.

>> Can we then use any dimes?
>> Can we then use any dimes?

Well, no-- because $0.07 mod $0.10 gives us a remainder of 7.
Well, no-- because $0.07 mod $0.10 gives us a remainder of 7.

10 doesn't go into 7 at all.
10 doesn't go into 7 at all.

>> Then can we use nickels?
>> Then can we use nickels?

Well $0.07 mod 5 cents gives us two remaining.
Well $0.07 mod 5 cents gives us two remaining.

And lastly, can we use any pennies?
And lastly, can we use any pennies?

2 mod 1 gives us 0, which is ultimately what
2 mod 1 gives us 0, which is ultimately what

we want because then that means that we've returned
we want because then that means that we've returned

to the user all of the change owed.
to the user all of the change owed.

>> So now you have two possible ways of implementing the greedy algorithm--
>> So now you have two possible ways of implementing the greedy algorithm--

one with loops and one with a combination of modulo and division.
one with loops and one with a combination of modulo and division.

So finally, we just need to print the final number of coins.
So finally, we just need to print the final number of coins.

>> If I wanted to tell you that I had 3 pets and this value was hardcoded,
>> If I wanted to tell you that I had 3 pets and this value was hardcoded,

then I could just use a simple print test statement.
then I could just use a simple print test statement.

But our value is actually stored in a variable.
But our value is actually stored in a variable.

So how do you print the values stored in variables?
So how do you print the values stored in variables?

>> For this we take advantage of placeholders.
>> For this we take advantage of placeholders.

Say I had already declared an initialized integer n.
Say I had already declared an initialized integer n.

Then later on if I wanted to print that value, then I would write the string.
Then later on if I wanted to print that value, then I would write the string.

And instead of that value I would use a placeholder for that integer-- %i.
And instead of that value I would use a placeholder for that integer-- %i.

Then after the string, I have a comma, followed by the variable
Then after the string, I have a comma, followed by the variable

that I want to print.
that I want to print.

And later on, when it prints, it'll print the value of n.
And later on, when it prints, it'll print the value of n.

>> I could also use a placeholder for a float, for instance.
>> I could also use a placeholder for a float, for instance.

If I wanted to tell you how much cash I have in my pocket,
If I wanted to tell you how much cash I have in my pocket,

then I could say I have %f dollars.
then I could say I have %f dollars.

And later on when it prints, then n will take the place of that place holder.
And later on when it prints, then n will take the place of that place holder.

I could also, for instance, use several placeholders for several variables.
I could also, for instance, use several placeholders for several variables.

So as long as I list them in order, then I
So as long as I list them in order, then I

can tell you how many dogs and cats I have.
can tell you how many dogs and cats I have.

>> Now we know how to prompt the user for an amount of change,
>> Now we know how to prompt the user for an amount of change,

ensure that that input is valid, and then we
ensure that that input is valid, and then we

have two possible ways of implementing the greedy algorithm of always using
have two possible ways of implementing the greedy algorithm of always using

the largest coin possible.
the largest coin possible.

Because we've kept track of how many coins we're using,
Because we've kept track of how many coins we're using,

we can then print that value at the end, telling the user how many coins they're
we can then print that value at the end, telling the user how many coins they're

getting back.
getting back.

>> My name is the Amayla, and this is CS50.
>> My name is the Amayla, and this is CS50.