algorithm - Bin-packing, arrange bins to pack n objects

Question

Here is a excise from The book "Algorithm Design Manual".

In the bin-packing problem, we are given n metal objects, each weighing between zero and one kilogram. Our goal is to find the smallest number of bins that will hold the n objects, with each bin holding one kilogram at most.

The best-fit heuristic for bin packing is as follows. Consider the objects in the order in which they are given. For each object, place it into the partially filled bin with the smallest amount of extra room after the object is inserted. If no such bin exists, start a new bin. Design an algorithm that implements the best-fit heuristic (taking as input the n weights w1,w2,...,wn and outputting the number of bins used) in O(nlogn) time.

Ok, this excise seems not hard. My initial understanding is that for the best-fit heuristic approach, I just every time look for a bin with minimum available space and try to put the object in. If the object does not fit to the bin with minimum space, I create a new bin.

I can build a BST to store the bins and each time when an object is put into a bin, I can delete that bin from the tree, update the bin's available space and re-insert the bin to the tree. This will mains O(logN) for every object placement.

However, I noticed the bold and italic part of the excise "For each object, place it into the partially filled bin with the smallest amount of extra room after the object is inserted".

So this means I am not looking for a bin which has minimum available space, instead, I am looking for one that if I place the current object in, the resulting available space (after placing the object) will be minimum.

For example, if bin1's current space is 0.5, bin2 is 0.7. So currently, bin1 is the minimum one. But if the current object is 0.6, then the object can't be placed into bin1, instead of creating a new bin, I have to find bin2 to put the object as bin2 - object = 0.7 - 0.5 = 0.2 which is then minimum.

Am I right? Does the bold part of the statement really mean like what I thought? Or is it just as simple as "find a bin with minimum space, if can place the object, then place; if can't, then create a new bin"?

Thanks

Edit: adding part of my java code for my new understanding of the bold part.

public void arrangeBin(float[] w) {
   BST bst = new BST();
   bst.root = new Node();

   int binCount = 0;
   for (int i = 0;i < w.length;i++) {
      float weight = w[i];
      Node node = bst.root;
      float minDiff = 1;
      Node minNode = null;
      while(node!=null) {
         if (node.space > weight) {
             float diff = node.space - weight;
             if (minDiff > diff) {
                 minDiff = diff;
                 minNode = node;
                 node = node.left;
             }
         }
         else 
             node = node.right;
      }
      if (minNode == null) {
         binCount++;
         Node node = new Node();
         node.space -= weight;
         bst.insert(node);
      }
      else {
         minNode.space -= weight;
         bst.delete(minNode);
         bst.insert(minNode);
      }
   }
}

Your code goes over all the nodes for each new weight, which would result in running time of O(N2). If you want to achieve O(nlogn) you should use something like I suggested in my answer. other than that it looks correct. — WeaselFox

WeaselFox WeaselFox · Accepted Answer · 2012-03-27T15:10:20

You need to keep a sorted array (or rather a sorted binary tree like a red-black tree) of bins sorted by remaining space, and for each new weight find the bin with the best fit of empty space in it in O(log(n)), and re-insert it to the tree also in O(log(n)). Your observation seems correct - you need to find the bin which best fits your new weight. Hope this helps.

algorithm - Bin-packing, arrange bins to pack n objects

2 Answers