The algorithm they're using must be "Until you hit the limit, take the highest denomination coin that fits beneath the limit. If you can't hit the limit, fall back one step."

That fits your definition of "use as many coins as possible of a given large denomination before dropping back to the next-lower denomination" but will find 10-10-10-1-1-1-1-1-1-1 and stop before it even tries 10-9-anything.

There is no greedy solution to the problem. A greedy algorithm would start by taking 3 10-cent coins to make 37 which is wrong.

> Wouldn't a properly-implemented greedy algorithm use as many coins as possible of a given large denomination before dropping back to the next-lower denomination?

Yes, and it won't work on the problem described. The greedy algorithm only works on certain sets of coins (US coin denominations are one of those sets), and fails in at least some cases with other coin sets (as illustrated in the bit you quoted).

D'oh, that makes sense, I didn't consider the case where it would keep returning 10.

It's in numerous algorithms textbooks and probably a lot of code repositories, so that's not surprising.

I didn't mean it was surprising. I meant literally what I said: I tried it, and it worked. Nothing more, nothing less.

Interesting that an informative comment, without any implications or insinuations, got downvoted.

HN sucks sometimes. "Intellectual discourse" and "hacker curiosity" my ass.

I voted you back up. It's the least I could do. :)