A friend of mine says that with the cash box given he can prove that
the greedy approach always works EXCEPT that if the greedy algorithm
would select an ODD number N of 500's, 50's 5's, or 0.25s, then the
algorithm must also try N-1 of the same denomination. This is because
they are congruent to 1 mod 2 of the next lower denomination. I think
I agree with him.
If you need to be able to change denominations without doing a proof
about properties of the new set and rewriting your code, then a good
approach is a branch-and-bound search that backtracks after greedily
trying the biggest denominations.
The question is how to bound the search so that it doesn't explode when
you give it a sum that is impossible. There are at least two rules
that make sense. (There might well be others.)
1. If you ever end up at a point where (due to backtracking) you have
less money available than the sum you are trying to pay out, then cut
the search and backtrack. Here is an example:
S = 51
Cashbox
2 x 20
1 x 10
1 x 5
The algorithm starts out by trying 2x20+10+5. This fails so it
backtracks in order to try 1x20. At that point there is only
20+10+5=35 remaining to use (2x20 already failed), so immediate
backtracking is the right thing to do.
2. Suppose you have paid out a partial amount A < S using cashbox
slots with denominations >= D and that afterward the search for a way
to pay out the rest (S - A) fails. This tells you that if you ever
find a different way to pay out A using denominations >= E where E <=
D, you should cut and backtrack immediately. This follows from trying
the most greedy solution first. An example would be
S = 101
Cashbox
1x50
2x20
1x10
25x5
After the search has tried 1x50 and then failed and backtracked, it
will later try 2x20+10. At this point it has reached 50 again, so it
can cut and backtrack because it is certain to fail the same way it did
last time.
So here is perl code that implements what I am talking about. It uses
a hash to store the sums it has already found and an array to decide
when the remaining cash smaller than the sum.
Of course for some sets of denominations and sums the size of the hash
table and the run time can become exponential, but I expect that for
your denominations it will work ok. I have not tested it very well.
Note I had to use integers to prevent floating point roundoff from
causing problems.
---------------------------
use strict;
# cashbox (denoms X 100 )
our @denom = (50000,20000,10000,5000,2000,1000,500,100,100, 50, 25, 10,
5, 1);
our @avail = (100, 40, 10, 100, 100, 44,
20,100,100,100,100,100,100,100);
# array of cumulative cashbox values defined as follows:
# cum_cb_val[i] = sum_{j = i to end} of avail[j] * denom[j]
our @cum_cb_val;
# current payout constructed by search
our @payout;
# sums where we have tried before and failed;
# value is the highest slot index used in the sum
our %dead_end_sum;
# branch-and-bound search for $sum using cashbox slots $i and greater
# if a search is successful, this prints and exits the program, else
# if search fails, this returns so that the search can continue
sub search {
my ($sum, $i) = @_;
# check for success
if ($sum == 0) {
print
join(", ",
map { $_->[0] ? sprintf("%d x %.2f", $_->[0], $_->[1]/100) :
() }
@payout);
exit;
}
# bound search if cumulative cashbox remaining is smaller than sum.
return if $cum_cb_val[$i] < $sum;
# find largest number of bills from slot that fit in sum
my $n = int($sum / $denom[$i]);
# don't use more than available
$n = $avail[$i] if $n > $avail[$i];
# try successively smaller values down to zero as long as search fails
while ($n >= 0) {
# find new sum after paying out $n bills from slot $i
my $new_sum = $sum - $n * $denom[$i];
# unless we have reached this sum before a different way
if (not exists $dead_end_sum{$new_sum} || $dead_end_sum{$new_sum} >
$i) {
# record our payout
push @payout, [$n, $denom[$i]];
# remove bills from cash box
$avail[$i] -= $n;
# search to find rest of sum
search($new_sum, $i + 1);
# recursive search failed, so restore bills to cash box
$avail[$i] += $n;
pop @payout;
# record that this sum is a dead end to cut of future searches
$dead_end_sum{$new_sum} = $i;
}
# try one less note/coin from this slot
--$n;
}
# all tries failed; backtrack!
}
# initialize the cumulative cashbox value array
sub init_cum_cb_val {
my @d = @denom;
my @a = @avail;
my $cum = 0;
while (@d) {
$cum += pop(@d) * pop(@a);
unshift(@cum_cb_val, $cum);
}
push(@cum_cb_val, 0);
}
# run the search!
init_cum_cb_val;
search int($ARGV[0] * 100 + .5), 0;
# search failed, so tell the user
print "Can't be done.\n";
