Ok, I looked at the description in the ML page you provided -- It's about 3/4 of the way down the page. I'll reproduce it here:
What is at issue is that the obvious "greedy" algorithm for making change that proceeds by doling out as many coins as possible in decreasing order of value does not always work. Given only a 5 cent and a 2 cent coin, we cannot make 16 cents in change by first taking three 5's and then proceeding to dole out 2's. In fact we must use two 5's and three 2's to make 16 cents. Here's a method that works for any set of coins: 
exception Change

fun change _ 0 = nil
  | change nil _ = raise Change
  | change (coin::coins) amt =
    if coin > amt then
       change coins amt
    else
       (coin :: change (coin::coins) (amt-coin))
       handle Change => change coins amt

[download]
The idea is to proceed greedily, but if we get "stuck", we undo the most recent greedy decision and proceed again from there. Simulate evaluation of the example of change [5,2] 16 to see how the code works.
With that in mind, I have written something in Perl that parallels his solution as closely as I could: 
use strict;
use warnings;

my $amount = 16;
my $coinset = [5,2];

{
  my $Exception = 0;

  sub change {
    my ($cset, $amt) = @_;
    if ($amt == 0)    { return [] }
    if (@$cset == 0)  { $Exception = 1; return [] }
    my $coin = shift @$cset;
    if ($coin > $amt) {
      print "$coin > $amt\n";
      return [change($cset, $amt)];
    }
    else {
      print "Checking $amt - $coin\n";
      my $rval = [$coin, @{change( [$coin, @$cset], $amt - $coin )}];
      if ($Exception) {
        print "Exception forces backing up to $amt\n";
        $Exception = 0;
        $rval = [@{change($cset, $amt)}];
      }
      return $rval;
    }
  }
}

use Data::Dumper;
print Dumper(change($coinset, $amount)), "\n";

[download]
Caution: Contents may have been coded under pressure.

In reply to Re: pathsearch/backtracking in Perl - how to solve a problem apparently requiring it? (comparison of Perl with Standard ML) by Roy Johnson
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.