Thread: 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.

Originally Posted by AfterShock

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

You're going to have to define "greedy"

do you mean using the largest coins possible?

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.

Originally Posted by AfterShock

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

Originally Posted by AfterShock

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

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.