Here is a excise from The book "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.
Ok, this excise seems not hard. My initial understanding is that for the best-fit heuristic approach, I just every time look for a bin with minimum available space and try to put the object in. If the object does not fit to the bin with minimum space, I create a new bin.
I can build a BST to store the bins and each time when an object is put into a bin, I can delete that bin from the tree, update the bin's available space and re-insert the bin to the tree. This will mains O(logN) for every object placement.
However, I noticed the bold and italic part of the excise "For each object, place it into the partially filled bin with the smallest amount of extra room after the object is inserted".
So this means I am not looking for a bin which has minimum available space, instead, I am looking for one that if I place the current object in, the resulting available space (after placing the object) will be minimum.
For example, if bin1's current space is 0.5, bin2 is 0.7. So currently, bin1 is the minimum one. But if the current object is 0.6, then the object can't be placed into bin1, instead of creating a new bin, I have to find bin2 to put the object as bin2 - object = 0.7 - 0.5 = 0.2 which is then minimum.
Am I right? Does the bold part of the statement really mean like what I thought? Or is it just as simple as "find a bin with minimum space, if can place the object, then place; if can't, then create a new bin"?
Thanks
Edit: adding part of my java code for my new understanding of the bold part.
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);
}
}
}
An optimal solution to a bin-packing problem uses the fewest number of bins possible. For example, given the set of elements 6, 12, 15, 40, 43, 82, and a bin capacity of 100, we can assign 6, 12, and 82 to one bin, and 15, 40, and 43 to another, for a total of two bins.
There are many simple algorithms that use the following general scheme: For each item in the input list: If the item fits into one of the currently open bins, then put it in one of these bins; Otherwise, open a new bin and put the new item in it.
The full bin packing algorithm is more likely to produce an optimal solution – using the least possible number of bins – than the first fit decreasing and first fit algorithms. It works by matching object so as to fill as many bins as possible.
Bin packing involves packing a set of items of different sizes in containers of various sizes. The size of the container shouldn't be bigger than the size of the objects. The goal is to pack as many items as possible in the least number of containers possible.
You need to keep a sorted array (or rather a sorted binary tree like a red-black tree) of bins sorted by remaining space, and for each new weight find the bin with the best fit of empty space in it in O(log(n)), and re-insert it to the tree also in O(log(n)). Your observation seems correct - you need to find the bin which best fits your new weight. Hope this helps.
The bold statement really does mean what you think it does.
The idea would be to find the fullest bin the current object will fit into, hence minimising the amount of wasted space. If the object doesn't fit in any bins then a new bin needs to be created
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With