|
Response Details:
I couldn't find the greedy algorithm in my discrete math book, but from what I can tell, the greedy algorithm is based on an iterative function, which for our purposes means that it will do the same thing over and over again until it solves the problem. For purposes of giving change, it works exactly the way that we work when we're thinking about giving change. You want to subtract from your total amount of change the highest coin that you can, which makes your problem smaller and smaller, until you don't have any change left to give.
a)87 cents
87 cents - 1 quarter = 62 cents - 1 quarter = 37 cents - 1 quarter = 12 cents - 1 dime = 2 cents - 1 penny = 1 cent - 1 penny = 0 cents.
3 quarters, 1 dime, 2 pennies total = 6 coins.
b)49 cents
49 cents - 1 quarter = 24 cents - 1 dime = 14 cents - 1 dime = 4 cents - 1 penny = 3 cents -1 penny = 2 cents - 1 penny = 1 cent - 1 penny = 0 cents. (Note that nickels are not an option, so you go down to the next increment of change that will fit in the remaining amount of change)
1 quarter, 2 dimes, 4 pennies total = 7 coins.
c)99 cents
99 cents - 1 quarter = 74 cents - 1 quarter = 49 cents (At this point, follow the steps in b)
2 quarters + 1 quarter,2 dimes, 4 pennies = 9 coins
d)33 cents
33 cents - 1 quarter = 8 cents - 1 penny = 7 cents - 1 penny = 6 cents - 1 penny = 5 cents - 1 penny = 4 cents -1 penny =3 cents - 1 penny = 2 cents - 1 penny = 1 cent - 1 penny = 0 cents.
1 quarter, 8 pennies = 9 coins
Now you can go back and look to see which solutions were the most efficient.
a) a solution with only 1 quarter would have required at least 9 coins, 2 quarters would have required 12 coins, and no quarters would have required at least 15 coins, so it looks like our solution for 87 cents was the most efficient.
b) a solution without quarters would have required 13 coins, so it looks like our solution for 49 cents was the most efficient.
c)We know that after we subtract 50 cents, we will have the same problem as in b, which we know is the most efficient solution, so you just have to ask if we subtracted 50 cents in the most efficient manner. We used two quarters, but we could have used 5 dimes or 50 pennies. It looks like we're good here too.
d)If we did not use a quarter, we could have used 3 dimes and 3 pennies = 6 coins to total 33 cents. It looks like here the greedy algorithm failed us, and caused us to use 3 more coins than we needed.
|