Bin packing problem
Calculator solves bin packing problem by different heuristic algorithms. Created at the request of the user.
This calculator is about Bin packing problem.
In other words, there are a fixed volume containers and a set of objects of any size (of course, the volume of each item individually smaller than the volume of the container). It's required to pack the items in the minimum number of containers.
There is another "life" example - there is a set of files (e.g., movies) of different sizes. It's required to copy all these movies on the least number of DVDs. And so on.
This is an NP-problem, which means finding the optimal solution needs a complete listing. However, there are heuristic algorithms for finding appropriate solutions. If you're lucky, it will be optimal :)
Here are a calculator and algorithms described below. And by the way, though on the default data some solutions are the same, the algorithms are still different, and with other data will be noticeable differences
Bin packing problem
Set of elements for packaging
| | | ||
|---|---|---|---|
Let's start with Next Fit Algorithm.
Next Fit Algorithm
In most cases, the algorithm is very dull and gives the worst results of all the considered algorithms.
The essence of the algorithm is as follows:
- Take a new element
- Take a new container.
- Put the element in the container.
- Take the next element.
- If the element fits into a container, go to step 3. If the item does not fit into the container, go to step 2.
So we just bluntly put elements in a container, and if one of them doesn't fit, we take a new container.
It's possible to develop a better algorithm, but this one has a positive side - it doesn't require checking previous containers. It can be useful if, e.g., the containers come to us on a conveyor belt.
First Fit Algorithm
The essence of the algorithm is as follows:
- Take a new element
- Take a new container.
- Put the element in the container.
- Take the next element.
- If the element fits into a container, go to step 3. If the element does not fit into the container, check the other containers in order. If there is a container with enough space, put it into the container and go to step 4, otherwise go to step 2.
That is, put an element in a container, and if the element is no longer fit, try to find a suitable container among the already partially filled. If we can't find a place, we take a new container.
Worst Fit Algorithm
The essence of the algorithm is as follows:
- Take a new element.
- Take a new container.
- Put the element in the container.
- Take the next element.
- If the element fits into a container, go to step 3. If the element does not fit into a container, take a partially filled container with maximum free space. If the element fit in a container, put the item into the container and go to step 4, otherwise go to step 2.
To summarize, put elements in the container, and if the item is no longer fits, try to put it in the least-filled container. If this fails, we take a new container.
Best Fit Algorithm
The essence of the algorithm is as follows::
- Take a new element
- Take a new container.
- Put the element in the container.
- Take the next element.
- If the element fits into a container, go to step 3. If the element does not fit into a container, take a partially filled container with a minimum of space but still fit the item. If there is such a container, go to step 3; otherwise, go to step 2.
To summarize, put elements in the container, and if the item is no longer intermeddle, trying to put it in a container filled the most, but there is still enough space for this item. If it fails, we take a new container.
Also, I should mention a variant with decreasing pre-sorting - First Fit Decreasing, Best Fit Decreasing, etc. It's the same, but the elements are chosen to start with the largest one. So, I've reviewed 8 algorithms, but the calculator only uses 4 - all of them are pre-sorting because they provide the best results.
Comments