I was reading some fascicles of Knuth's volume 4 on combinatorial enumeration. It seems that he was using Binary Decision Diagrams (BDDs) and variations to calculate quickly similar numbers. Perhaps this will help.
Also, your description suggests to me that solutions will exist, that they can be found greedily, and that optimizing them may gain very little for the effort involved. For example, to get a representation involving many of the stamp values, I would start by forming partial sums of the stamp values in increasing order until I came close to the target or ran out of values. Then I would use standard methods to represent the difference, and voila, I have made the target using the most stamp values possible. If you want a better answer than this, provide a couple of explicit examples to communicate the feel of the problem (e.g. "using stamps in prime values from 23 to 199 cents, make 2010 cents in postage without using more than two of any single denomination, while using as few of the stamps over 100 cents as possible") .
There also were some recent papers in arxiv.org that talked about algorithms used
to solve the postage stamp problem with large stamp values. It may be that some dual exists where you can use large numbers of small stamp values to accomplish your goal.
I hope this "soft answer" jogs some neurons into something that will work for you.
Gerhard "Ask Me About System Design" Paseman, 2010.01.15
No comments:
Post a Comment