APL - Need an Algorithm

Author

Need an Algorithm

Doug White

2008-03-16, 7:06 pm

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

2008-03-16, 7:06 pm

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
>

graham

2008-03-16, 7:06 pm

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

Don Wiss

2008-03-16, 7:06 pm

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

Doug White

2008-03-16, 7:06 pm

Keywords:
In article <o1kqt3heoigj6tmv64qdh6t8q0nquti64g@4ax.com>, Don Wiss <donwiss@no_spam.com> wrote:
>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

Doug White

2008-03-16, 7:06 pm

Keywords:
In article <47dd31d3$0$25476$ba620dc5@text.nova.planet.nl>, "jk" <*axy*@planet.nl (remove the 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 am I
>wrong?

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

Doug White

Doug White

2008-03-16, 7:06 pm

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

Doug White

2008-03-16, 7:06 pm

Keywords:
In article <dOudncZLRvyYwEDanZ2dnUVZ_o3inZ2d@rcn.net>, gwhite@alum.mit.edu (Doug White) wrote:
>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

Don Wiss

2008-03-16, 7:06 pm

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

Don Wiss

2008-03-16, 7:06 pm

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

Curtis A. Jones

2008-03-16, 7:06 pm

Doug,
A function I called SNS (select number of stamps?) takes a vector of
stamp values as the left argument and the total desired value as the
right argument and gives columns with the number of stamps of each
value. One would usually pick the column with the smallest sum.

e.g.
0.01 0.02 0.05 SNS 0.07
0 1 2 3 5 7
1 3 0 2 1 0
1 0 1 0 0 0

Here's the listing using APL2ASCII. I split lines [1] and [6], so you
may have to put them back together for APL2ASCII to assemble the
function.

The technique is a fairly brute force application of outer product,
but it's been useful. Curtis

{del}SNS[#]{del}
{del}
[0] Z{<-}A SNS B;C;D;#IO
[1] @ Select number of stamps of denominations A
for total value B.
[2] @ CAJ 19 DEC 1987.
[3] @ Maximum number of stamps of each denomination.
[4] C{<-}{floor}B{divide}A{<-},A
[5] #IO{<-}D{<-}0
[6] L2:{->}(({rho}A){<=}{rho}{rho}D{<-}D{jot}.+
A[{rho}{rho}D]{times}{iota}1+C[{rho}{rho
}D]){drop}L2
[7] Z{<-}({rho}D){represent}(,D=B)/{iota}{times}/C+1
{del} 1995-01-25 23.04.00 (GMT-7)

James J. Weinkam

2008-03-17, 6:59 pm

Doug White wrote:
> 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
>
If you drop the word slightly from requirement 1 or quantify it by
saying, for example, no more than 5 percent, your problem is an integer
programming problem. Surely there is an APL integer programming
application out there somewhere.

I would be inclined also to drop the words or exceeds. Its still an
integer programming problem but more economical.

In either case, if the problem has no solution its time to stock up on
stamps.

It might be even better to look into buying or leasing a postage meter.
Then you can use exact postage every time with only one sticker to apply
and no stamp inventory to fool with.

Seth

2008-03-20, 6:59 pm

In article <WuydncUdgIRJt0DanZ2dnUVZ_jmdnZ2d@rcn.net>,
Doug White <gwhite@alum.mit.edu> wrote:

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

The general problem is NP-complete.

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

There are heuristics, often of bounded badness.

There are solvable special cases.

Seth

Don Wiss

2008-03-20, 6:59 pm

Doug White

2008-03-20, 6:59 pm

Keywords:
In article <qft5u3p17l3mh62a54hi11uvtid0i499fv@4ax.com>, Don Wiss <donwiss@no_spam.com> wrote:
>On Sun, 16 Mar 2008 18:40:08 GMT, gwhite@alum.mit.edu (Doug White) wrote:
>
>
>Hi Doug,
>
>How are you making out with your problem?

With my wife hammering on taxes this time of year, I've been doing a lot
of the household chores & teenager taxi service, so I haven't had a
chance to work on it for several days.

Graham Steer provided me with a "knapsack" function that works very
nicely. I've built a simple cover function for it. It's in APL+WIN, and
I now need to learn enough about creating an executable to cobble
something together to run as a standalone program. I've been wanting to
do this for years, and now my wife can't complain too loudly about my
taking the time.

I also have a function from Russ Swain, but it seems to have lost
something in translation. I need to figure out what's busted and fix
that. At some point I want to dissect both programs enough to understand
how they work.

Doug White

Sponsored Links