An interesting wrinkle to this is that an 18 cent coin would make it much harder to make change with the fewest coins for certain values.
How do we make change in everyday life? The simple algorithm everyone knows, even if they don't know what an algorithm is, is to start with the largest coin and move down, taking as many of each as you can. Thus to make change for 72 cents we:
take 2 quarters, leaving us with 22 cents
take 2 dimes, leaving us with 2 cents
take no nickels
take 2 pennies, leaving us with 0 cents and we're done
This algorithm as it turns out is only optimal so long as each denomination is at least twice as much as the previous one. So what happens if we have an 18 cent coin? Let's make change for 37 cents. With the simple algorithm we end up with {1 quarter, 1 dime, 2 pennies}. That's four coins. However you can do it with three coins: {2 18 cent pieces, 1 penny}.
The algorithm for the case with arbitrary denominations isn't np-complete (it's a fun algorithms question to figure out), but it's way too difficult to be doing in your head all the time.
How do we make change in everyday life? The simple algorithm everyone knows, even if they don't know what an algorithm is, is to start with the largest coin and move down, taking as many of each as you can. Thus to make change for 72 cents we: take 2 quarters, leaving us with 22 cents take 2 dimes, leaving us with 2 cents take no nickels take 2 pennies, leaving us with 0 cents and we're done
This algorithm as it turns out is only optimal so long as each denomination is at least twice as much as the previous one. So what happens if we have an 18 cent coin? Let's make change for 37 cents. With the simple algorithm we end up with {1 quarter, 1 dime, 2 pennies}. That's four coins. However you can do it with three coins: {2 18 cent pieces, 1 penny}.
The algorithm for the case with arbitrary denominations isn't np-complete (it's a fun algorithms question to figure out), but it's way too difficult to be doing in your head all the time.