Doug,
Wasn't there a suitable example in An Interactive Approach - something
with
innner product (dot plus (.+ ...), distances or shortest path, maybe. Or
am I
wrong?
Jan
"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
>
|
