Keywords:
In article <dOudncZLRvyYwEDanZ2dnUVZ_o3inZ2d@[EMAIL PROTECTED]
>, gwhite@[EMAIL PROTECTED]
(Doug White) wrote:
>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.
I looked up the "knapsack problem", and this is indeed the sort of
problem I'm faced with. Wikipedia has a nice description:
http://en.wikipedia.org/wiki/List_of_knapsack_problems
It would appear that I am fighting with something very close to the
"change making problem". There appear to be plenty of references &
articles to dig through. Google has over 1300 hits on it. There are
several references to "polynomial-time" algorithms, which is a new one on
me.
It at least appears that I have opened a well-established can of worms
here, now that I know what to call it.
Doug White
|
