алгоритм - Bin-packing, расставить бины для упаковки n объектов

Вот выдержка из книги "Algorithm Design Manual".

В задаче об упаковке в мусорное ведро нам дано n металлических предметов, каждый из которых весит от нуля до одного килограмма. Наша цель — найти наименьшее количество контейнеров, в которых можно хранить n предметов, причем каждый контейнер может содержать не более одного килограмма.

Наиболее подходящая эвристика для упаковки в контейнер выглядит следующим образом. Рассмотрим объекты в том порядке, в котором они даны. Для каждого объекта поместите в частично заполненную корзину с наименьшим количеством лишних комната после вставки объекта. Если такой корзины не существует, запустите новую мусорное ведро Разработайте алгоритм, реализующий эвристику наилучшего соответствия. (принимая на вход n весов w1,w2,...,wn и выводя число используемых бинов) за время O(nlogn).

Хорошо, этот акциз кажется несложным. Мое первоначальное понимание состоит в том, что для наилучшего эвристического подхода я просто каждый раз ищу корзину с минимальным доступным пространством и пытаюсь поместить объект. Если объект не помещается в корзину с минимальным пространством, я создаю новый мусорное ведро

Я могу построить BST для хранения бинов, и каждый раз, когда объект помещается в бин, я могу удалить этот бин из дерева, обновить доступное пространство в бине и снова вставить бин в дерево. Это будет составлять сеть O (logN) для каждого размещения объекта.

Тем не менее, я заметил полужирную и курсивную часть акциза «Для каждого объекта поместите его в частично заполненную корзину с наименьшим количеством дополнительного места после того, как объект будет вставлен».

Таким образом, это означает, что я не ищу корзину с минимальным доступным пространством, вместо этого я ищу такую, в которой при размещении текущего объекта результирующее доступное пространство (после размещения объекта) будет минимальным.

Например, если текущий объем ячейки 1 равен 0,5, то размер ячейки 2 равен 0,7. Итак, в настоящее время bin1 является минимальным. Но если текущий объект равен 0,6, то объект не может быть помещен в корзину 1, вместо создания новой корзины я должен найти корзину 2, чтобы поместить объект как корзину 2 - объект = 0,7 - 0,5 = 0,2, что тогда минимально.

Я прав? Действительно ли выделенная жирным шрифтом часть утверждения означает то, что я думал? Или это так же просто, как «найти корзину с минимальным пространством, если можно поместить объект, то поместить; если нельзя, то создать новую корзину»?

Спасибо

Редактировать: добавлена ​​часть моего 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);
      }
   }
}