Bin packing problem

The bin packing problem is an NP-complete problem in mathematics. In it, objects of different volumes must be packed into a finite number of bins of capacity V in a way to minimize the number of used bins.

There are a lot of variations of this problem (2D packing, linear packing, packing by weight, packing by cost, etc...) most of them with many applications, such as filling up containers, loading trucks with weight capacity, creating file backup in removable media, etc...

Since it is NP-complete, the most efficient algorithms use heuristics to accomplish very good results in most cases, which may not be the optimal solution. The Best Fit Decreasing and First Fit Decreasing strategies use no more than 11/9 OPT + 4 bins (where OPT is the number of bins given by the optimal solution).

See also

• Packing problem
• Knapsack problem