算法 - Bin-packing,排列bin以包装n个对象

Question

这是" 算法设计手册 " 一书中的一个消息.

在装箱问题中,我们给出了n个金属物体,每个物体的重量在0到1千克之间.我们的目标是找到容纳n个物体的最小数量的箱子,每个箱子最多可容纳1公斤.

bin包装的最佳拟合启发式如下.按照给定顺序考虑对象.对于每个对象,将其放置与额外的空间的量最小的部分填充箱的对象被插入后.如果不存在此类bin,则启动新bin.设计一种算法,该算法在O(nlogn)时间内实现最佳拟合启发式(将n个权重w1,w2,...,wn作为输入并输出所使用的二进制数).

好吧,这个消费税似乎并不难.我最初的理解是,对于最合适的启发式方法,我只是每次寻找具有最小可用空间的bin并尝试将对象放入.如果对象不适合具有最小空间的bin,我创建一个新的完事.

我可以构建一个BST来存储垃圾箱,每次将一个对象放入垃圾箱时,我可以从树中删除该垃圾箱,更新垃圾箱的可用空间并将垃圾箱重新插入树中.这将为每个对象放置提供O(logN).

然而,我注意到消费税的粗体和斜体部分"对于每个物体,在插入物体后将其放入部分填充的箱子中,并留出最少量的额外空间".

所以这意味着我不是在找一个具有最小可用空间的bin,相反,我正在寻找一个如果我将当前对象放入其中,结果可用空间(放置对象之后)将是最小的.

例如,如果bin1的当前空间为0.5,则bin2为0.7.所以目前,bin1是最小的一个.但是如果当前对象是0.6,那么对象不能放入bin1,而不是创建一个新的bin,我必须找到bin2把对象作为bin2 - object = 0.7 - 0.5 = 0.2,这是最小的.

我对吗？声明的大胆部分是否真的像我想的那样？或者它就像"找到一个具有最小空间的bin,如果可以放置对象,然后放置;如果不能,那么创建一个新的bin"这么简单？

谢谢

编辑:为我对粗体部分的新理解添加部分Java代码.

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);
      }
   }
}

Answer 1

您需要保留一个按剩余空间排序的已排序数组(或者更确切地说是一个类似红黑树的已排序二进制树),并且对于每个新权重,在O中找到具有最佳空白空间的bin (log(log( n)),并在O(log(n))中将其重新插入树中.您的观察结果似乎是正确的 - 您需要找到最适合您新体重的垃圾箱.希望这可以帮助.