Results 1 to 9 of 9

Thread: Greedy Change-making Algorithm

  1. #1
    Join Date
    Oct 2009
    Posts
    0
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Greedy Change-making Algorithm

    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.

  2. #2
    Join Date
    Mar 2006
    Location
    Illinois, USA
    Posts
    12,164
    Thanks
    265
    Thanked 690 Times in 678 Posts

    Default

    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.
    Daniel - Freelance Web Design | <?php?> | <html>| espa˝ol | Deutsch | italiano | portuguŕs | catalÓ | un peu de franšais | some knowledge of several other languages: I can sometimes help translate here on DD | Linguistics Forum

  3. #3
    Join Date
    Oct 2009
    Posts
    0
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default

    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.

  4. #4
    Join Date
    Mar 2005
    Location
    SE PA USA
    Posts
    30,495
    Thanks
    82
    Thanked 3,449 Times in 3,410 Posts
    Blog Entries
    12

    Default

    Al Gore has no rhythm.
    - John
    ________________________

    Show Additional Thanks: International Rescue Committee - Donate or: The Ocean Conservancy - Donate or: PayPal - Donate

  5. #5
    Join Date
    Mar 2006
    Location
    Illinois, USA
    Posts
    12,164
    Thanks
    265
    Thanked 690 Times in 678 Posts

    Default

    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.
    Daniel - Freelance Web Design | <?php?> | <html>| espa˝ol | Deutsch | italiano | portuguŕs | catalÓ | un peu de franšais | some knowledge of several other languages: I can sometimes help translate here on DD | Linguistics Forum

  6. #6
    Join Date
    Mar 2005
    Location
    SE PA USA
    Posts
    30,495
    Thanks
    82
    Thanked 3,449 Times in 3,410 Posts
    Blog Entries
    12

    Default

    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.
    - John
    ________________________

    Show Additional Thanks: International Rescue Committee - Donate or: The Ocean Conservancy - Donate or: PayPal - Donate

  7. #7
    Join Date
    Mar 2006
    Location
    Illinois, USA
    Posts
    12,164
    Thanks
    265
    Thanked 690 Times in 678 Posts

    Default

    I think this actually allows "The Tortoise and the Hare" to be a relevant metaphor in programming. Interesting.
    Daniel - Freelance Web Design | <?php?> | <html>| espa˝ol | Deutsch | italiano | portuguŕs | catalÓ | un peu de franšais | some knowledge of several other languages: I can sometimes help translate here on DD | Linguistics Forum

  8. #8
    Join Date
    Mar 2005
    Location
    SE PA USA
    Posts
    30,495
    Thanks
    82
    Thanked 3,449 Times in 3,410 Posts
    Blog Entries
    12

    Default

    Quote Originally Posted by djr33 View Post
    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.
    - John
    ________________________

    Show Additional Thanks: International Rescue Committee - Donate or: The Ocean Conservancy - Donate or: PayPal - Donate

  9. #9
    Join Date
    Mar 2006
    Location
    Illinois, USA
    Posts
    12,164
    Thanks
    265
    Thanked 690 Times in 678 Posts

    Default

    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.
    Daniel - Freelance Web Design | <?php?> | <html>| espa˝ol | Deutsch | italiano | portuguŕs | catalÓ | un peu de franšais | some knowledge of several other languages: I can sometimes help translate here on DD | Linguistics Forum

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •