algorithm - Bin-packing，排列箱子来打包 n 个对象

Question

这是《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.

好吧，这个消费税似乎并不难。我最初的理解是，对于最适合的启发式方法，我只是每次都寻找一个可用空间最小的容器并尝试将对象放入。如果对象不适合最小空间的容器，我会创建一个新的容器垃圾箱。

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

但是，我注意到消费税的粗体和斜体部分“对于每个对象，插入对象后”，将其放入具有最小额外空间的部分填充的容器中。

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

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

我说的对吗？声明中加粗的部分真的和我想的一样吗？还是说“找一个空间最小的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

您需要保留一个按剩余空间排序的 bin 的排序数组(或者更确切地说是像红黑树这样的排序二叉树)，并且对于每个新权重，在 < strong>O(log(n))，并在 O(log(n)) 中将其重新插入到树中。您的观察似乎是正确的——您需要找到最适合您新体重的箱子。希望这会有所帮助。