Greedy Algorithms Walkthrough

[00:00:00]
>> Bianca Gandolfo: Let's just say that you're a banker in Monopoly. Your family, they just lose all their game pieces so you need to make sure, so they only have 3 bills, first of all. You have a $5 bill, a $10 bill and a $25 bill for some reason. And whenever you pay out your family, you wanna make sure that you're using the least number of bills because once you run out of bills, Monopoly is over.

[00:00:23]
Okay, so how might you write an algorithm to solve this problem? This is one version of the make change problem which is the same thing except you'll see different versions of this. So it'll be Monopoly money or it'll be coins or it'll be weight, something like that, where you need to minimize or maximize something.

[00:00:45]
And in this case, we wanna minimize the number of coins that add up to our amount. So in this case, it's always gonna be divisible by 5.
>> Bianca Gandolfo: Because otherwise it wouldn't work, okay? So if our input is 40, and we would want a output of 3, right?

[00:01:07]
So it would be 25, 10, and 5. And if our input is 35, it would 2, 25 and 10. So your task right now is to write a function, make change, such that we get the correct,
>> Bianca Gandolfo: Result.
>> Bianca Gandolfo: All right,
>> Bianca Gandolfo: Good luck.
>> Bianca Gandolfo: So the greedy solution to something like the make change problem is to simply choose the largest coin that you can at any given time.

[00:01:55]
So if you're starting with 40, you're gonna pick the largest one, 25. So you're gonna subtract 40 minus 25, what do you have left? 15, so then you're gonna do that again, subtract 10, subtract 5. So this is the greedy algorithm. And it seems reasonable right? It works in this scenario for 40, it's gonna give us the right answer.

[00:02:17]
And here is how you might do that. You can sort the coins first if you'd like. And then you're just gonna do this while loop. While you have a certain amount, you're gonna decrement the largest coin you possibly can and keep going with that. It seems pretty straightforward.