Results 1 to 7 of 7

Math Help - Greedy Algorithm

  1. #1
    Senior Member
    Joined
    Apr 2006
    Posts
    401

    Greedy Algorithm

    In our money system, does it ALWAYS pay to be greedy to use the feweset amount of coins. For example, if something is costs 40cents, we would use 1 quarter, 1 dime, 1 nickel and that would be the least amount of coins used to get it (we assume we're only using nickels, dimes, quarters, pennies..we dont worry about half dollars etc).

    I can't think of any examples that wouldn't work.

    I can think of example (not our money system) where it wouldn't pay to be greedy. For instance, if we had pennies, nickels, dimes, 20 cents, and quarters...

    for 40 cents we could just use 2 20 cents' instead of the quarter, then dime, then nickel...

    So, does it always pay to be greedy in our money system? Is there a general rule, like perhaps the previous coin amount has to be half the first or something to that excent... just some thoughts.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    dan
    dan is offline
    Member dan's Avatar
    Joined
    Jun 2006
    From
    nebraska usa
    Posts
    113

    Talking

    Quote Originally Posted by AfterShock View Post
    In our money system, does it ALWAYS pay to be greedy to use the feweset amount of coins. For example, if something is costs 40cents, we would use 1 quarter, 1 dime, 1 nickel and that would be the least amount of coins used to get it (we assume we're only using nickels, dimes, quarters, pennies..we dont worry about half dollars etc).

    I can't think of any examples that wouldn't work.

    I can think of example (not our money system) where it wouldn't pay to be greedy. For instance, if we had pennies, nickels, dimes, 20 cents, and quarters...

    for 40 cents we could just use 2 20 cents' instead of the quarter, then dime, then nickel...

    So, does it always pay to be greedy in our money system? Is there a general rule, like perhaps the previous coin amount has to be half the first or something to that excent... just some thoughts.

    i don't understand... i like to use as many coins as i can to pay for things ...then my pants are't so heavy...6_6


    dan
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor Quick's Avatar
    Joined
    May 2006
    From
    New England
    Posts
    1,024
    You're going to have to define "greedy"

    do you mean using the largest coins possible?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Apr 2006
    Posts
    401
    Greedy as in you pick the highest amount every time...

    So, for 30 cents, you would pick the quarter, and then the nickel...

    For 50 cents, you would pick 2 quarters..

    86 cents... 3 quarters, 1 dime, 1 penny...

    And so forth.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by AfterShock View Post
    In our money system, does it ALWAYS pay to be greedy to use the feweset amount of coins. For example, if something is costs 40cents, we would use 1 quarter, 1 dime, 1 nickel and that would be the least amount of coins used to get it (we assume we're only using nickels, dimes, quarters, pennies..we dont worry about half dollars etc).
    Since the Internet is not confined to the United States I suggest you
    give the actual values of these coins as a number of your potential
    readers won't know what they are.

    RonL
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by AfterShock View Post
    In our money system, does it ALWAYS pay to be greedy to use the feweset amount of coins. For example, if something is costs 40cents, we would use 1 quarter, 1 dime, 1 nickel and that would be the least amount of coins used to get it (we assume we're only using nickels, dimes, quarters, pennies..we dont worry about half dollars etc).


    We wish to prove that the greedy algorithm will give change in the
    minimum number of coins.

    I will assume that the coins in question are 25, 10, 5 and 1 cent.

    Suppose otherwise, then there is a minimum counter example N.

    1. N must be divisible by 5, and the minimal change will contain no 1's,
    as will the greedy change.

    2. Suppose that N>25, and that U=(u25, u10, u5) is the minimal change vector.
    That is 25*u25+10*u10+5*u5=N, and u25+u10+u5 is a minimum among
    all change vectors for N. Also let V=(v25, v10, v5) be the greedy change
    vector.

    Then u25=0, since otherwise N-25 would be a smaller counter example.

    Now if N>=30 the minimal change vector must comprise at least three
    coins, and they must contain at least either 3 tens, or 2 tens and 2 fives,
    or 1 ten and 4 fives, of 6 fives. In any of these cases the coin count can
    be reduced by replacing three or more coins by one 25 and one 5 which
    contradicts the assumption that U is the minimum change vector.

    So assuming N>25 forces us to conclude that N<30, but N is divisible
    by 5, a contradiction. so N<25 (it cant be =25 as the greedy algorithm
    is optimal for this).


    Now a similar argument can be constructed for the case 10<N<25, which
    I will leave to the reader (because I am lazy and am now bored of typing ).

    The case N<10 can then be disposed of by enumeration


    RonL
    Last edited by CaptainBlack; September 28th 2006 at 08:02 AM.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Senior Member
    Joined
    Apr 2006
    Posts
    401
    Sorry; in this case I was referring to our monetary system as (1 cents, 5 cents, 10 cents, and 25 cents), which is a penny, nickel, dime, and a quarter, respectively.

    I'll read over your thoughts. Thanks CaptainBlack.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Greedy Algorithm Proofs
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: August 22nd 2010, 09:26 PM
  2. Greedy Learning
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: March 2nd 2009, 02:51 AM
  3. Greedy Algorithm for license purchase problem
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: November 15th 2008, 09:19 PM
  4. Greedy algoritm problem
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 7th 2008, 09:05 AM
  5. Algorithm
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: February 26th 2007, 05:42 AM

Search Tags


/mathhelpforum @mathhelpforum