Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

You find yourself in a country with integer coin denominations $c_1 < c_2 < ... < c_r$, where $c_1 = 1$. Unfortunately, the greedy algorithm is not guaranteed to find the optimal way to make change. Let $C(i)$ be the minimum number of coins needed to make change for $i$ cents.

(a) Find a recurrence for $C$.

(b) Write an algorithm for computing an array OPT$[0...n]$ where OPT$[i]$$ = C(i)$.

I'm not really sure how to go about doing this. What does the information about the greedy algorithm tell us about the behavior of the problem? How can we use the information given to write a recurrence for $C(i)$?

share|improve this question
2  
The information about the greedy algorithm basically just tells you how not to approach the problem. –  Brian M. Scott Dec 17 '12 at 2:44

3 Answers 3

It is a typical problem in Dynamic Programming. You can check Dynamic Programming Solution to the Coin Changing Problem.

share|improve this answer

Suppose you are making change amount $Z$ and you can't do it with only one coin. Then $Z = X + Y$, and you've already calculated the optimum amount for $X$ and $Y$. So just check all possible $X$ and $Y$ pairs.

share|improve this answer

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";
}
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.