Beefy Boxes and Bandwidth Generously Provided by pair Networks
Welcome to the Monastery

Re: Computer science Problem - single dimension bin packing

by sundialsvc4 (Abbot)
on Aug 14, 2014 at 17:33 UTC ( #1097462=note: print w/replies, xml ) Need Help??

in reply to Computer science Problem - single dimension bin packing

Quite honestly, I would duck-and-dodge the problem since there is probably no measurable advantage to an “optimal solution.”   I’d say, just choose at random any bin that is big-enough to hold the next object.   Any garden-variety random number generator is designed to provide a fairly-even distribution of generated values, so the odds are quite good that the actual distribution obtained for any particular backup will be favorable.

You could also, of course, add a second “back-fill” pass to the algorithm, which examined the initial random result to see if it is obviously-screwy, as in a particular bucket being (say ...) “more than some-n standard deviations away from the mean,” in which case you might, for example, make a random number of attempts to successfully “steal” a randomly-selected item (that will fit ...) from a randomly-chosen bucket in order to drop it into the bucket(s) that are coming-up “short.”

A little bit of simulation should help you determine whether your chosen compromise-algorithm is “good enough for peace work.”

  • Comment on Re: Computer science Problem - single dimension bin packing

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://1097462]
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others surveying the Monastery: (6)
As of 2018-06-25 10:06 GMT
Find Nodes?
    Voting Booth?
    Should cpanminus be part of the standard Perl release?

    Results (126 votes). Check out past polls.