Need an Algorithm

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)

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.

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

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.

Hi Doug,

How are you making out with your problem?

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

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