Keywords:
In article <j8udndePhatqrkDanZ2dnUVZ8tignZ2d@[EMAIL PROTECTED]
>, "graham"
<h2gt2g42-news@[EMAIL PROTECTED]
> wrote:
>
>"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.
I'm not familiar with the "knapsack problem", but it sounds very
applicable. I'd love to see your solution. I think I have APL+WIN v3,
so I don't know if I will be able to open a workspace directly. Does
APL+WIN allow saving to an earlier file format? Another option would be
to save it to a file transfer format of soem flavor.
The email address on my postings is valid (no spam protection).
Thanks!
Doug White
|
