Sample

Bin packing problem# Bin packing problem

##### Calculator solves bin packing problem by different heuristic algorithms. Created at the request of the user.

Recently, user Artuem left an interesting request - .

Here it is: "There are a number of segments of different lengths, it is necessary to calculate the minimum number of boards from which they can be cut or something like that :)"

After some thoughts, you can agree that this is Bin packing problem.

In other words, there is 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, but the algorithms are still different, and with other data will be noticeable differences

Let's start with Next Fit Algorithm.

**Next Fit Algorithm**

The algorithm is very dull, and in most cases give 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 the 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 to check 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 a next element.
- If the element fit 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 the item 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 a next element.
- If the element fit into a container, go to step 3. If the element does not fit into a container, take a partially filled container with a 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.

That is 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 a next element.
- If the element fit 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 which is still able to fit the item. If there is such a container, go to step 3, otherwise go to step 2.

That is, put elements in the container, and if the item is no longer intermeddle, trying to put it in a container filled the most, but in which there is still enough space for this item. If it fails, we take a new container.

Also, I should mention that there is 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 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