Bin packing problem

The container or bin packing problem is a combinatorial optimization problem which is based on the following question:

• Given: A number of " containers " (I'm English) the size and a number of "Objects" with the weights ( sizes).
• Question: Can the will, "objects" as the " container " distributed ( packing ) that none of the " tank " overflows?

The decision problem described above is NP- complete; the corresponding optimization problem - finding an allocation, in which minimizes the number of containers - is NP-hard.

The here given formulation of the bin packing problem is the motivation or base for a variety of other packing problem, which play an important role, among others, in the packaging industry.

A more general formal definition describes the bin -packing problem as the determination of a partition and assignment of a set of objects, so that while a specific condition or an objective function is minimized or maximized.

Algorithms

Since bin-packing is an NP- hard problem, it is probably impossible to solve it in polynomial running time. Johnson's approximation algorithm First Fit Decreasing solves the problem in polynomial time with a sharp asymptotic guarantee of quality (not asymptotically is the quality guarantee).

Sort the objects in order of decreasing weight Add the objects in order after one,   so that each is given in the first container in which there is room.   If there is enough space in any of the already -opened container, open a new one. The running time ( both for sorting, as well as for the paste). The same results also apply Best Fit Decreasing. An object is not inserted in the first container in which it fits, but in the container in which it only just fits ( the remaining capacity is thus minimized).

If it must be decided for each object immediately, into which container it comes, it is called the online variant of the bin packing problem. It is therefore not possible to sort the objects in advance by weight. The algorithms First Fit and Best Fit work similar to the above but without prior sorting. Both algorithms have a sharp asymptotic quality guarantee of 1.7 and a period of.

By The naive algorithm Next Fit packs the objects of the series in the last open container, if they fit. Otherwise, the container is closed, a new open and if the current object in the empty container. The asymptotic quality guarantee period is 2, the running time. The advantage of this naive algorithm is that only one container is open at the same time (which may be a condition in practical application ).