My wife works out of the house (accounting & taxes), and frequently needs
to mail thick envelopes of papers. She has a postal scale that will tell
her the correct postage, but she then needs to come up with the right
collection of stamps that:
1) Just equals or slightly exceeds the required postage
2) Uses the values she has on hand
3) Uses the fewest stamps
Being an accountant, she hates using anything more than the exact
postage, but being vaguely rational, she doesn't want to stick 20 one
cent stamps on an envelope either.
I foolishly told her "I can write a little APL routine to do that". I've
been thinking about it for a while, and it's not nearly as simple as I
thought.
For inputs, there will be the desired postage, and a vector of available
stamp values. I figure you want to start with multiples of the highest
stamp value, and then work your way down in value(s) to minimize the
number of stamps. Other possible inputs could be the maximum number of
stamps acceptable and the "comparison tolerance" of how much over the
exact amount is OK.
Other than doing a Monte Carlo routine or an exhaustive search (which can
get pretty messy), I haven't come up with a tidy algorithm. It should (I
think) be possible to come up with a function that gets called
iteratively (possibly by itself) to chase down the best combinations, but
that's about where my brain starts hurting.
In the interest of domestic harmony, does anyone have any brainstorms of
a clean way to approach this? I'm hoping to be able to use APL*PLUS/PC
so I can make a runtime executable for her. I have an old copy
of APL+Win, but haven't ever had time to get familiar with it, so a
regular "APL I" soution would be best. There is probably a sexy way to
do it with nested arrays in APL II, but that will take a while for me to
figure out how to package into an exectutable.
Thanks!
Doug White
|
