Beefy Boxes and Bandwidth Generously Provided by pair Networks
Clear questions and runnable code
get the best and fastest answer
 
PerlMonks  

Re: Challenge: Twist On Bin Packing

by kvale (Monsignor)
on Apr 07, 2006 at 16:49 UTC ( [id://541916]=note: print w/replies, xml ) Need Help??


in reply to Challenge: Twist On Bin Packing

First, lets order the bins 1 through N. I'll call a packing 1-stable if no set of single elements can be moved from later bins B to earlier bins A to reduce the muber of bins used. In this sense the OP solution is is 1-stable: the 2 cannot be moved to an earleir bin.

If there is no ordering requirement, the OP soultion is not stable: I can move the 5 and the 2 to the fourth bin, the 3 to the first bin and the 4 to the third bin to eliminate a bin. So, the OP must be thinking about the ordered case.

Simialrly, suppose 2-stable allows both sinlge moves and transpositions. Then the 2 and 3 of the first and third bins can be excahnged and then 2 in the fourth bin can be moved into the third bin, reducing the number of bins. So the OP must be only thinking about single moves.

To solve the ordered 1-stable problem, I suggest, sorting the gifts from smallest to largest and then fill up bins using sequential elements from the sorted list. For the OP example, (2, 2, 3, 4, 5, 6, 7) this would give

1: 2,2,3 2: 4,5 3: 6 4: 7
which gives the same maximum number of bins, but spreads the gifts about more evenly. Intuitively, by using up all the smallest elements that could be used to fill up the interstices first, the remaining bins will be taken up by larger elements with lots of empty space.

-Mark

Replies are listed 'Best First'.
Re^2: Challenge: Twist On Bin Packing
by japhy (Canon) on Apr 07, 2006 at 16:57 UTC
    I agree; the least-to-greatest gives the highest magnitude (number of bins).

    Jeff japhy Pinyan, P.L., P.M., P.O.D, X.S.: Perl, regex, and perl hacker
    How can we ever be the sold short or the cheated, we who for every service have long ago been overpaid? ~~ Meister Eckhart
      Smallest to largest won't always give the maximum number of bins. Take 1,1,1,2,2,3,4,6,7,7 for example.

      Filling them smalles to largest you get 4 bins:
      1,1,1,2,2,3
      4,6
      7
      7

      But you can get 5 bins by filling it:
      6,1,1,1
      2,2,3
      7
      7
      4
        Well, crap. You should un-anonymize yourself so I know who to hatethank.

        Jeff japhy Pinyan, P.L., P.M., P.O.D, X.S.: Perl, regex, and perl hacker
        How can we ever be the sold short or the cheated, we who for every service have long ago been overpaid? ~~ Meister Eckhart
        Ack! Neat! Can you describe the algorithm?
      It seems that L~R has some work cut out to compare the Least-to-Greatest method with any other contenders, on a large enough set of random samples, and tell us if there are any interesting anomalies. [Well, it is his problem, and I have to get some work done before home-time ;]

      -QM
      --
      Quantum Mechanics: The dreams stuff is made of

      This is cool. The least-to-greatest approach will indeed give a larger number of bins than the approach I posted above under some circumstances, so this may be the winner. However, it will also lead to larger variability in the contents of the bins and could lead to more bins being, for example, 51% full. Ultimately the relative importance of "filling the bins as close to capacity as possible" and "maximizing the number of bins" remains somewhat unclear.

Log In?
Username:
Password:

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

How do I use this?Last hourOther CB clients
Other Users?
Others learning in the Monastery: (None)
    As of 2024-04-25 00:10 GMT
    Sections?
    Information?
    Find Nodes?
    Leftovers?
      Voting Booth?

      No recent polls found