Greedy Change-making Algorithm

[BurnM3W1thF1r3]

Background: Greedy Change-making algorithm
say we want to make 84 cents with least amount of coins.
Step 1, Use the most of the largest value coin
Step 2, Use the most of the 2nd largest
Step 3, etc
Example: 84 cents US currency, 3 quarters (most without going over), can't use dimes, 1 nickle (most amount without going over), and 4 pennies (most without going over).

Problem: we chose to figure out ways to make this algorithm fail, so in the example, (if there was a 21 cent piece, the algorithm would fail).

42 cents: 1 quarter, 1 dime, 1 nickle, 2 pennies. (Greedy change making algorithm)
42 cents: 2 21-cent pieces
Algorithm fails.

So we are supposed to find a cent value that will make this algorithm fail if we cannot use the nickle. Quarters, Dimes, and Pennies.

[djr33]

Is this homework? We're not going to do homework for you. There's no point if you're not doing the work yourself-- that's why you get homework... to learn. If you can't do it, all the more reason you should learn how.

I'm pretty sure you have the steps there: loop through the coins until you'd go over, and move to the next one. Once you reach 84 cents, stop and output the results.

If the algorithm fails, then you can loop through and remove (one of) the largest coin from your stack and start over-- only use 2 quarters, for example. And repeat. If you eventually remove using the last of your smallest coins, then you can't make the goal amount (like if there were no pennies, you could not make 84 cents).

As for finding an amount, that's just trial and error, or you could write a program that would test different values. Think outside the box a bit and you'll get there.

As is, though, I don't really understand how it can fail. Regardless of what you add as long as it never goes above 84 cents, the pennies should be able to make up the difference.

[BurnM3W1thF1r3]

i was not asking to be given an answer and thats it, I was asking to be explained how to do this so I can learn... I did not understand entirely what to do and I was seeking help so that I could understand the concept, however after consulting with classmates who also did not understand it, we came to the conclusion of 2 possible answers 30 and 40... But thanks for the non help, and not explaining the situation. the reason it fails on both those numbers is as follows.

Since you cannot use a nickle (or 5 cent piece) 30 cents would be 1 quarter (25) and 5 pennies (5 1's) which makes 6 pieces, HOWEVER, the least amount of coins to make 30 cents is 3 dimes. Which causes the greedy algorithm to fail. Same with 40 cents (1 quarter, 1 dime, 5 pennies = 7 coins... or 4 dimes = 4 coins) Algorithm fails again. That is what we were trying to find, when it fails.

[jscheuer1]

Al Gore has no rhythm.

[djr33]

Realistically, then, it's just trial and error. Find it using the "greedy" method, then loop through each time removing one of the biggest coins. Then compare all methods and how many coins they take and find the smallest amount.
And as for finding which coins make it fail, that's just the inverse.

Frequently people will just ask for answers on homework, so I wanted to make it clear we do not just do homework for people. If that was not your intent, then there shouldn't be a problem. However, your reply is quite harsh, and there's no reason for that-- I gave my understanding, though it sounds like you already understand it-- so why are you asking if you know better than we do?
Do you actually want to design a program that does this or do you just want to understand how it fails? It sounds like you already understand that, and writing the program would be difficult. It would probably be faster just using a pen and paper, actually.

[jscheuer1]

I think you hit on it perhaps djr33. Maybe if you kept taking away the two largest coins and looped through again until there were no more coins that are allowed that could be removed in this manner, all the while keeping track of the total number of coins required in each scenario and comparing those results to find the smallest. Well let's just say, "Al Gore might be very happy."

And the short answer as to why it (the original approach) doesn't always work is simply that it doesn't take into account all of the possible combinations of the allowed coins.

[djr33]

I think this actually allows "The Tortoise and the Hare" to be a relevant metaphor in programming. Interesting.

[jscheuer1]

I think this actually allows "The Tortoise and the Hare" to be a relevant metaphor in programming. Interesting.

If all you were concerned with was weight, would you rather have a pound of feathers or a pound of lead.

[djr33]

Certainly a pound of lead... keeping track of that many feathers would be annoying. Then again, lead poisoning and all that... perhaps I'll go with the feathers.