"Doug White" <gwhite@[EMAIL PROTECTED]
> wrote in message
news:WuydncUdgIRJt0DanZ2dnUVZ_jmdnZ2d@[EMAIL PROTECTED]
> 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
Just a thought but could you use a version of the knapsack algorithm with
the weight and volume in the classic solution both set equal to the stamp
values and the numer of each item equal to the number of stamps of each
value your wife has. If you round the cost calculation to the minimum
value
stamp available that might help with the solution given your three
constraints above. Here's an example with classic parameters in
parentheses:
Stamp values (weights) $10 5 2 1
Stamp values (volumes) $10 5 2 1
Stamp numbers (items) 10 10 10 10
Required total value $49
Made up by stamps 4x10 1x5 2x2 0
If you think that might work I have written a function to solve the
knapsack
problem which I could dig out and send you but it is in APL+WIN v5. If you
are interested let me have your e-mail address and I will mail you direct.
Graham.
|
