Puzzle part 6: Outline of the solution

We want to write a function with the following declaration:

Seq<unsigned> dealstamps(cents c, const Seq<cents>& denoms);

Here, cents is an unsigned type that is appropriate to represent a number of cents. This function should return a sequence with one element for each element in denoms, representing how many stamps of each denomination there are.

If the problem can't be solved, we'll return an empty Seq. Our caller can check whether the result is empty to see whether the function worked.

If we were to pass an empty denomination sequence, of course, the result would be empty regardless; we'll consider that the caller's problem.

We begin by defining a variable to hold the result:

Seq<size_t> result;

If denoms is empty, either the problem has no solution or c is zero; either way the result is an empty sequence.

if (denoms.empty())
    return result;

Now we pick off the first denomination; if it's zero, we have no work to do.

const cents firstdenom = denoms.head();
if (firstdenom == 0)
    return result;

Now we have a first denomination and a number of cents. The maximum number of stamps will therefore be c/firstdenom. We'll also keep track in bestsum of the smallest total count of stamps we've seen so far, and in result of the corresponding number of each stamp. Until we see the first solution, bestsum will be infinity:

const size_t maxcount = c / firstdenom;
size_t bestsum = 0; bestsum = ~bestsum;

We will now proceed to work through every possible number of stamps for that first denomination.

for (size_t n = 0; n <= maxcount; ++n) {
    const cents remainder = c - n * firstdenom;

Here, remainder is the number of cents not accounted for by the stamps of the first denomination. We now call ourselves recursively to see if we can allocate the remainder among the rest of the denominations.

    const Seq<unsigned> s = dealstamps(remainder, denoms.tail());

If remainder was zero, this call might return an empty sequence; but we must treat it as success anyway. Otherwise, it is successful if it returns a nonempty sequence. Either way, we check whether this solution was better than the one we had so far. If so, we remember the new solution:

    if ((remainder == 0 || !s.empty()) && n + sum(s) < bestsum) {
        result = cons(n, s);
        bestsum = n + sum(s);
    }
}

return result;

And that's basically it.

Of course, we still need to write the Seq template. We'll leave that as an exercise.

Posted by Andrew Koenig at 12:09 PM  Permalink