Need an Algorithm

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

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@alum.mit.edu> wrote in message
 news:WuydncUdgIRJt0DanZ2dnUVZ_jmdnZ2d@rc
n.net...
> 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
>

"Doug White" <gwhite@alum.mit.edu> wrote in message
 news:WuydncUdgIRJt0DanZ2dnUVZ_jmdnZ2d@rc
n.net...
> 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.

On Sun, 16 Mar 2008 15:12:37 GMT, gwhite@alum.mit.edu (Doug White) wrote:

>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.

I have written something similar. It looks at a bunch of folders in a
folder and finds the best fit that is just less than the size of the DVD
that I want to burn them to. The logic I follow is a bit hard to explain
here. It is in APL+Win 7.2. I don't think it will load under version 5. So
I've sent you PDF printouts of the two main functions. They are amply
commented.

Don <www.donwiss.com> (e-mail link at home page bottom).

Keywords:
In article <o1kqt3heoigj6tmv64qdh6t8q0nquti64g@4ax.com>, Don Wiss <donwiss@no_spam.com> wro
te:
>On Sun, 16 Mar 2008 15:12:37 GMT, gwhite@alum.mit.edu (Doug White) wrote:
> 
>
>I have written something similar. It looks at a bunch of folders in a
>folder and finds the best fit that is just less than the size of the DVD
>that I want to burn them to. The logic I follow is a bit hard to explain
>here. It is in APL+Win 7.2. I don't think it will load under version 5. So
>I've sent you PDF printouts of the two main functions. They are amply
>commented.

Thanks Don!  I've got them, and will go through them and try to sort out
the underlying logic.  It's a little different problem, but should be
similar enough to the stamp problem to be a help.  The big difference is
that you wouldn't put multiple copies of a file on a DVD.

Doug White

Keywords:
In article <47dd31d3$0$25476$ba620dc5@text.nova.planet.nl>, "jk" <*axy*@planet.nl (remove t
he asterisks)> wrote:
>Doug,
>
>Wasn't there a suitable example in An Interactive Approach - something with
>innner product (dot plus (.+ ...), distances or shortest path, maybe.  Or a
m I
>wrong?

Possible.  I've got it here and will check.

Doug White

Keywords:
In article <j8udndePhatqrkDanZ2dnUVZ8tignZ2d@bt.com>, "graham" <h2gt2g42-news@yahoo.co.uk> 
wrote:
>
>"Doug White" <gwhite@alum.mit.edu> wrote in message
> news:WuydncUdgIRJt0DanZ2dnUVZ_jmdnZ2d@rc
n.net... 
>
>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 knapsac
k
>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

Keywords:
In article <dOudncZLRvyYwEDanZ2dnUVZ_o3inZ2d@rcn.net>, gwhite@alum.mit.edu (Doug White) wro
te:
>Keywords:
>In article <j8udndePhatqrkDanZ2dnUVZ8tignZ2d@bt.com>, "graham"
> <h2gt2g42-news@yahoo.co.uk> wrote: 
>
>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

On Sun, 16 Mar 2008 18:40:08 GMT, gwhite@alum.mit.edu (Doug White) wrote:

>Thanks Don!  I've got them, and will go through them and try to sort out
>the underlying logic.  It's a little different problem, but should be
>similar enough to the stamp problem to be a help.  The big difference is
>that you wouldn't put multiple copies of a file on a DVD.

Yep. I figure in your set of what to pick from you can include multiple of
each denomination. But limit it to say four $0.01 stamps, so it doesn't use
lots of them.

You are also going to have to wade through a lot of irrelevant enhancements
that it has received along the way. But I think the overall logic of
testing possible sets will work.

What I do for mailing is I have a few denominations of large sizes. Then I
have $0.17, which the is extra ounce cost. Then I stock lots of $0.01,
0.02, and 0.03 to fill it up.

At one time I stocked the one-ounce stamp, the three ounce stamp, and a lot
of the extra ounce stamps. But they kept changing the amounts far faster
than I could use them up. Then they made it different for large and small
envelopes.

Don <www.donwiss.com> (e-mail link at home page bottom).

On Sun, 16 Mar 2008 18:46:46 GMT, gwhite@alum.mit.edu (Doug White) wrote:

>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.

Somewhere along the way, I think it was in version 5, they changed the
format.

>  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.

Yes. You have to use the ]OUT and the ]IN to transfer between incompatible
versions.

Don <www.donwiss.com> (e-mail link at home page bottom).