Beefy Boxes and Bandwidth Generously Provided by pair Networks chromatic writing perl on a camel
P is for Practical
 
PerlMonks  

Comment on

( #3333=superdoc: print w/ replies, xml ) Need Help??
There are about as many approaches to this problem as there are ways to make change for $100 ;) ... There are a few more examples/ideas in this thread: How to generate restricted partitions of an integer (the solutions towards the bottom are the ones that actually work!)

And for yet another opinion on the subject (s/coin/bill/ throughout the rest of this, if you prefer)... Just because it's a little simpler, I would first just try counting the ways to make change for the amount (i.e, without keeping track of what those ways are). To make change for an amount, I first choose which coin will be the biggest coin that I'm going to include, which can be any available coin. I subtract that coin from my total, and then I need to find how many ways I can make change for what's left over, using none of the coins bigger than the one I just chose (since it was supposed to be the biggest). Of course, that's just nothing more than a recursive subcall! In code it looks like this:

sub make_change { my ($N, @coins) = @_; return 0 if $N < 0; return 1 if $N == 0; my $total = 0; for (0 .. $#coins) { $total += make_change( $N-$coins[$_], @coins[$_ .. $#coins] ); } return $total; } print make_change( 100 => 50, 25, 10, 5, 1 );
Then instead of just counting, I'd modify the code to keep track of the choices it made so far (using an additional argument), and when it gets to the end, do something with them. This is called using an accumulator (I called it @so_far for this sub).
sub make_change { my ($N, $coins, $callback, @so_far) = @_; my @coins = @$coins; return if $N < 0; return $callback->(@so_far) if $N == 0; for (0 .. $#coins) { make_change( $N - $coins[$_], [@coins[ $_ .. $#coins ]], $callback, ($coins[$_], @so_far) ); } } make_change( 100, [50, 25, 10, 5, 1], sub { print "@_\n" } );
Cheers!

PS: here are two other cute money denomination puzzles I've posted about, if you're interested: Golf: Buying with exact change & The greedy change-making problem using regexes

blokhead


In reply to Re: puzzle: how many ways to make $100 by blokhead
in thread puzzle: how many ways to make $100 by davidj

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!
  • 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, 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, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • Outside of code tags, you may need to use entities for some characters:
            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.
  • Log In?
    Username:
    Password:

    What's my password?
    Create A New User
    Chatterbox?
    and the web crawler heard nothing...

    How do I use this? | Other CB clients
    Other Users?
    Others contemplating the Monastery: (5)
    As of 2014-04-16 04:22 GMT
    Sections?
    Information?
    Find Nodes?
    Leftovers?
      Voting Booth?

      April first is:







      Results (413 votes), past polls