By way of enrichment here is a solution in Perl that checks its arguments very carefully and otherwise tries to keep it simple. Here is a sample run for a common choice of denominations:
$ ./change.pl 100 1 2 5 10 20 50 1, 1, 2, 2, 1, 2, 2, 3, 3, 1, 2, 2, 3, 3, 2, 3, 3, 4, 4, 1, 2, 2, 3, 3, 2, 3, 3, 4, 4, 2, 3, 3, 4, 4, 3, 4, 4, 5, 5, 2, 3, 3, 4, 4, 3, 4, 4, 5, 5, 1, 2, 2, 3, 3, 2, 3, 3, 4, 4, 2, 3, 3, 4, 4, 3, 4, 4, 5, 5, 2, 3, 3, 4, 4, 3, 4, 4, 5, 5, 3, 4, 4, 5, 5, 4, 5, 5, 6, 6, 3, 4, 4, 5, 5, 4, 5, 5, 6, 6, 2
And this is the code.
#! /usr/bin/perl -w # MAIN: { my $n = shift; die "first argument is max value" if !defined($n); die "positive integer please: $n" if $n !~ /^\d+$/ || $n < 1; my @denoms = (); while(my $denom = shift){ die "not a positive number: $denom" if $denom !~ /^\d+$/; die "zero denomination: $denom" if $denom == 0; die "not in order/duplicate: $denom" if scalar(@denoms)>0 && $denom <= $denoms[-1]; push @denoms, $denom; } die "no denominations" if scalar(@denoms) == 0; my @OPT = ((undef) x ($n > $denoms[-1] ? $n : $denoms[-1])); unshift @OPT, 0; foreach my $denom (@denoms) { $OPT[$denom] = 1 }; for(my $val = 1; $val < scalar(@OPT); $val++){ my $choice = $OPT[$val]; foreach my $try (@denoms) { my $prev = $val - $try; last if $prev < 0; my $count = $OPT[$prev]; if(defined($count)){ if(!defined($choice) || $count+1 < $choice){ $choice = $count + 1; } } } $OPT[$val] = $choice if defined($choice); } shift @OPT; print join ', ', map {defined($_) ? $_ : 'X'} @OPT; print "\n"; }