C Program Greedy Algorithm Efficient (Making Change)

hey guys so in this video I want to create the greedy algorithm using the C program to make the least amount of change I did a video on this before but this time I want to make it a little bit more efficient so it's going to get started I'm going to write a description here of the permanent verb outer right it's gonna say this program gives the least amount of USD coins for a given amount and then they'll put efficiently because this hopefully this program is a little bit more efficient and then let's put a little note the USD coin set is 50 we actually have 100 as well we have a hundred 50 25 10 5 and 1 so these are the quarters the dimes the nickel and the pain and that's actually all I want to use I don't want to use these other two they're not too common so we're just gonna use these for coins for our coin set now let's include some libraries standard input/output dot H that's probably all that's needed let's go ahead and create our main function and I'm going to put in system pause because I am using a Windows operating system right now so if you're not using the Windows operating system you can comment this out or you can just completely delete that line of code so we're gonna start off with myself with it a mount so this would be the amount of change that we want to get back so I say something like 85 sits so what's the least amount of coins we can get back for 85 cents is the question we're gonna create our coin set and I'm gonna make it an array of size 1 2 C 1 2 3 4 so I'm gonna make it size 4 and it's going to be equal to 25 10 5 and 1 okay and I'm gonna create a variable we call it a number for the greedy calculations alright so now let's go ahead and create our greedy algorithm for making the least amount of change or not make us a instead of making printing already so since I'm just gonna print in this function I'm gonna make it void and call it greedy and it's gonna take an integer amount and all its gonna do is tell us how many of each coins we'll need the least amount of each points we'll need for the given amount so now to find that up there let's go ahead and and actually do something inside this function so something here that I already kind of see a problem with this this number 4 so what I'm going to do is I'm going to create a let's see I will create a global variable not call it lint or lint and it's going to equal 4 so this is the lint of our array or coin set not ready so now I can change this for out here for lint ok so now I'm here I will create an integer called I for it the index of our coin set and what we're going to do is say while while I is less than Lin we're gonna daughter stuff in here now right now there's a problem we didn't assign the value for I so let's say I go to 0 so this is going to run the length of the array times all right and I have my number variable here but actually we'll need it in the greedy algorithm alrighty so let's see now we're gonna go through all of the lists and what we want to do is put a little if statement so if our Wow I will actually need to put the coin set as well inside of our greedy algorithm so if our coin set at position I which would be position 0 which in this case would be the quarter which has the value 25 so if that if value of that coin is or the amount of the coin it's less than the amount that we are putting in and this is the same amount that we will put in here and I'm a from here into the greedy algorithm if it's less than or equal to that amount then our number it's going to equal the amount divide it by that coin so that coin at that position so right now our amount is or will be 85 so then number equals 85 divided by 25 which goes in there I think three times which tells us that really going to use three of the quarters or that value 25 so we really use that three times that's where the number variable comes in so now we're going to do a print statement and I am going to say you need our Alessi we're gonna print the number so percent D and all right I don't know how to I want to write this print statement maybe the number of coins that they need and we're going to print the value of that coin so so three of 25 is needed and I'll put a backslash in it for the next line so have you put in number and I can put in the coin I'm out so now here's a three of 25 is needed perfect then our I've al you needs to increase once it's done so I'm going to increment I by one by using I plus plus and then they'll go to the next value which is ten so there's something else I need to do here now what I need to do is I need to take that amount that we have and needs to equal the amount minus minus the number x times the coin at that position so in this case it will be since we're still in the quarter of the twenty five cents the amount is 85 so it's 85 minus the number which will be three times the coin at position I which is 25 so that's 75 so it's 85-75 so that gives us 10 so a mountain out equals 10 so now we're going to increment I so I is gonna go to the next value which is 10 and it's gonna say if coin set I is and that's the value 10 is less than or equal to 10 which is the amount 10 is also the amount right now then the number is going to equal 10 divided by 10 which is 1 so it's gonna say 1 of 10 since it's needed and then the amount is going to be 1 I'm sorry it will be 10 minus 10 which is 0 and then we're going to increment this here and it's gonna go back and we're going to be at 5 is 5 less than or equal to 0 no so they're going to increment again and then we go to the 1 it's one less than or equal to zero and the answer is no so they were done so let's go ahead and give this a whirl see if this actually works someone get the function here we're going to input our amount hopefully I don't have any errors let's see save it as a dot C program I'll call it greedy to or really efficient okay so let's see I have some problems here variable sized object I see if it likes this instead it doesn't let's see variable size object may not be initialized coin undeclared ah okay so we didn't call it coin called it coin set okay now let's run it okay so now let's see variable sized object may not be initialized okay variable sized well let's try let's try size five okay so it gives us exactly what we want it we want it three of 25 is needed and one of ten is needed so we would give the user 3/4 and we give the users one dime so I'm gonna clean this up just a little bit and I'm gonna put here another if statement or actually a few if coin set at position I equals equals 25 then we're going to print % d % d quarters instead of values actually we'll just put your quarters and then output the value inside the parentheses is needed and I'm just going to copy this here if coin set is 10 and I will say dimes and then if the coin set is 5 I want to put nickels and then if the coin set is 1 I'll put pennies and now let's get this run so three of quarters 25 is needed okay so at the end of this of okay and let's give it a run again three quarters 25 is needed one dimes I miss Phillip dimes I have two S's alright and now what I want to do is a print statement here or actually we can do that in the function as well before we do anything else we get to a press statement and we can say the least amount of change me it for the amount and then we're going to put the amount here is below and they'll claim the amount so awfully just makes it look a little bit better so the least amount of change need it for the amount 85 is below 3/4 one dimes and I'm actually gonna get rid of this is needed part as well let's write it again the least amount of change needed for the amount 85 is below 3/4 one dimes all righty and let's change the amount up just to just to kind of see if this is working properly so we have 99 cents the least amount of change would be three quarters two dimes which would be 75 95 and then four pennies so that's 99 cents so that works perfectly so thanks guys I hope this video was helpful and I will put this up on my github and put a link for it below so you can easily download it please subscribe please leave likes please become a support on patreon and thanks again for watching and I see you on the next video

You May Also Like