This was a math problem that my third-grade son was given in his math homework. The goal was to figure out the stamps needed to exactly match a certain number of cents. The original problem:
Tim had to mail the following packages:
- package 1 cost 42 cents
- package 2 cost 76 cents
- 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?
See my blog posts at http://data-ken.org/can-you-do-third-grade-math-part-1/ and http://data-ken.org/can-you-do-third-grade-math-part-2/ for a full explanation.
There are three solutions provided here:
- greedy.py - a greedy algorithm that does not always give the correct solution
- product.py - compute the correct solution by searching through the product of possible solution members
- dynamic.py - much better solution using dynamic programming