Doug White wrote:
> 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
>
If you drop the word slightly from requirement 1 or quantify it by
saying, for example, no more than 5 percent, your problem is an integer
programming problem. Surely there is an APL integer programming
application out there somewhere.
I would be inclined also to drop the words or exceeds. Its still an
integer programming problem but more economical.
In either case, if the problem has no solution its time to stock up on
stamps.
It might be even better to look into buying or leasing a postage meter.
Then you can use exact postage every time with only one sticker to apply
and no stamp inventory to fool with.
|
