|
|
|
|
|
|
by adamgordonbell
498 days ago
|
|
|
Yeah, greedy is not what he thinks it is. I think of change making algorithm when working retail. Greedy is you always use the largest coin you can, and then the next largest and so on. It works with sensible coin denominations but there are sets of coins where the greedy algorithm is not optimal. |
|
|
Looking at cases where greedy isn't optimal, I see two patterns. Either:
* there are two coins close in value (ratio of less than 2), e.g. both 20¢ and 25¢; or
* there is a "missing" coin at the GCD of two larger coins.
I'm pretty sure you can precompute extra "virtual coins" (e.g. 40¢) to make greedy optimal again, but you have to place restrictions on how many of them you're allowed to use.