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