Beefy Boxes and Bandwidth Generously Provided by pair Networks
There's more than one way to do things
 
PerlMonks  

Re: How can I calculate the right combination of postage stamps?

by MidLifeXis (Monsignor)
on Nov 26, 2008 at 15:27 UTC ( [id://726127]=note: print w/replies, xml ) Need Help??


in reply to How can I calculate the right combination of postage stamps?

Basically, this is very similar to a bin packing problem. Your fitness test is the minimum amount over the postage required, and your termination test is greater than or equal to the amount of postage required. Very commonly solved with a recursive or stack-based solution.

IIRC, with the exception of pruning paths once they reach the required postage, the only way to get all solutions is really brute-force. If you are satisfied with the first solution found, then you can trim that somewhat. This is, I believe, your classical NP-Complete problem, which, without some assumptions, is only solvable by brute force.

Very enjoyable (meaning interesting :-) post and problem, BTW.

--MidLifeXis

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://726127]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others scrutinizing the Monastery: (9)
As of 2024-03-28 09:10 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found