|
|
|
|
|
|
by o11c
501 days ago
|
|
|
Relevant link: https://en.wikipedia.org/wiki/Change-making_problem 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. |
|
|