Says Eimi Metamorphoumai:
Interestingly, that only gives you the smallest number of coins for certain combinations of denominations.
I looked into this in some detail a while back also. As you point out, the greedy change algorithm for the US (1, 5, 10, 25) system always delivers the minimum possible number of coins for any amount, but this is a property of the particular denominations used. Clearly, a system with coins of size 1, 10, and 11 does not have this property, since the greedy algorithm gives change for 20 cents by starting with an 11-cent coin, and then delivers nine pennies.

When I realized this I started to look around to see if there were any widely-used coinage systems that did not have the greedy property. I was pleased to discover one: the pre-decimalization currency of the United Kingdom included the following coins: 

    half-crown  =  30 pence
    florin      =  24 pence
    shilling    =  12 pence
    sixpence    =   6 pence
When changing four shillings = 48 pence, the greedy algorithm delivers a half-crown, a shilling, and a sixpence, but the optimal solution delivers two florins.

--
Mark Dominus
Perl Paraphernalia

In reply to Re: OT: making change by Dominus
in thread pathsearch/backtracking in Perl - how to solve a problem apparently requiring it? (comparison of Perl with Standard ML) by metaperl

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.