以下是書籍「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