Bin-Packing

Problem: Bin Packing

Description

The Bin Packing problem is an optimization problem. Given a set of items, $I$, where each item is associated with a label and a cost, i_x = (l, c) (size, weight, etc.), and a max bin capacity, c, find the smallest number of bins that will fit all items without exceeding any bin's capacity.

Example

If we have items I = {(1, 2), (2, 1), (3, 3), (5, 5)}, and a capacity c=6, we can pack our items optimally in 2 bins with:

• b₁ = {2, 5} and b₂ = {1, 3}.

In this case neither bin exceeds capacity (b₁ is filled 6/6 and b₂ is 5/6).

Related

See also the knapsack problem.