Can you do third-grade math? [part 1]

From time to time, my son will ask for help when he gets stuck on a math homework problem. Usually, it is pretty straightforward, and I can clear up any conceptual difficulties right away. Occasionally, I'm left wondering what they really expect from elementary school kids.

Last spring, my son came to me with the following math problem:

Tim had to mail the following packages:
  a) package 1 cost 42 cents
  b) package 2 cost 76 cents
  c) package 3 cost 94 cents

He had enough 10 cent, 22 cent, and 50 cent stamps to make up the
correct amount for each package. What was the least number of stamps
he needed to post each package?

An obvious way to solve this would be to use a greedy approach: pick as many 50-cent stamps as can fit with in the limit, then pick 22-cent stamps, and finally 10-cent stamps. This works fine for package 1 -- no 50-cent stamps, one 22-cent stamp, and two 10-cent stamps. Let's look at some Python code that uses this approach:

STAMP_SIZES = (50, 22, 10)

def greedy_solve(value, stamp_sizes=STAMP_SIZES):
    """Find the minimal list of stamps which add up the value, where
    stamps may have face values taken from stamp sizes.
    """
    # Ensure we check in descending order
    stamp_sizes = sorted(stamp_sizes, reverse=True)
    stamps = []
    total = 0
    for face_value in stamp_sizes:
        # Compute the most stamps of the value whose total
        # is below the amount left
        cnt = (value-total)/face_value
        if cnt==0:
            continue
        # repeat the current value cnt times
        stamps.extend([face_value]*cnt)
        total += (cnt*face_value)
        if total==value:
            return stamps

In the above code, greedy_solve() takes an instance of the  stamp problem (a goal value and a list/tuple of allowable stamp sizes) and returns a list of stamps equaling that value. Hopefully, this set of stamps is also the smallest number of stamps equaling the value. If we run greedy_solve() in the Python REPL for package 1, we get the the expected result:

>>> print greedy_solve(42)
print greedy_solve(42)
[22, 10, 10]

Let's try it for package 2:

>> print greedy_solve(76)
print greedy_solve(76)
None

Whoops! The greedy_solve() function did not find an answer. Is there no solution for package 2? If you think about it, three 22-cent stamps and one 10-cent stamp will add up to 76 cents. Thus, the greedy algorithm is not sufficient for this problem. Furthermore, we can also imagine cases of the stamp problem where the greedy algorithm gives a solution, but it is not optimal. Consider the case where we need 55-cents in postage and have 50-cent, 11-cent, and 1-cent stamps. Here's what we get when we run greedy_solve():

>>> greedy_solve(55, stamp_sizes=[50, 11, 1])
greedy_solve(55, stamp_sizes=[50, 11, 1])
[50, 1, 1, 1, 1, 1]

That solution requires 6 stamps. However, one can reach the 55-cent total by using only five 11-cent stamps.

Can you write a simple and efficient solution to the "stamps problem"? How hard is it anyway? In part 2, I discuss solutions and relate this to a standard problem in Computer Science Theory.