以下是书籍“Algorithm Design Manual”的摘录。算法 - 装箱，安排箱子打包n件物品
在装箱问题中，我们给出了n个金属物体，每个金属物体的重量在0到1千克之间。我们的目标是找到能容纳n个物体的最小数量的垃圾桶，每个垃圾桶最多可容纳1公斤。
bin包装的最佳拟合启发式如下。请按照给定顺序考虑 对象。 对于每个对象，将 放入部分填充的容器中，其中最小的额外容量为 ，该容器在插入对象后。如果不存在此类垃圾箱，请启动一个新的垃圾箱。设计一个算法，在O（nlogn）时间内实现最佳拟合启发式 （以n个权重w1，w2，...，wn作为输入并输出所使用的bin数 ）。
好的，这种消费似乎并不难。我最初的理解是，对于最适合的启发式方法，我只是每次都寻找一个具有最小可用空间的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，然后该值为最小值。
对吗？声明的大胆部分是否真的意味着我的想法？或者它就像“找到一个空间最小的物品，如果可以放置物品，然后放置;如果不能，然后创建一个新的箱子”一样简单？
感谢
编辑：加入我的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);
}
}
}
您的代码遍历每个新权重的所有节点，这会导致运行时间为O（N2）。如果你想达到O（nlogn），你应该使用我在我的答案中建议的内容。除此之外它看起来是正确的。 – WeaselFox 2012-03-27 15:33:02
@WeaselFox，我保持一个bst – 2012-04-02 11:05:58