Mathwords logoMathwords

Bin Packing — Definition, Formula & Example

Bin packing is the problem of fitting a list of items, each with a size, into the smallest possible number of containers (bins) that all have the same capacity.

Given a bin capacity C>0C > 0 and item sizes s1,s2,…,sns_1, s_2, \dots, s_n with 0<si≤C0 < s_i \le C, find a partition of {1,…,n}\{1, \dots, n\} into the fewest sets B1,…,BkB_1, \dots, B_k such that ∑i∈Bjsi≤C\sum_{i \in B_j} s_i \le C for every jj. The minimum kk is written OPT\text{OPT}. The decision version ("can the items fit in kk bins?") is NP-complete, so no polynomial-time algorithm is known that always finds OPT\text{OPT}.

Key Formula

OPT≥L=⌈s1+s2+⋯+snC⌉\text{OPT} \ge L = \left\lceil \frac{s_1 + s_2 + \cdots + s_n}{C} \right\rceil
Where:
  • LL = lower bound on the number of bins needed
  • sis_i = size of item i
  • CC = capacity of each bin
  • ⌈⋅⌉\lceil \cdot \rceil = ceiling: round up to the nearest integer

Worked Example

Problem: Pack items of sizes 7, 5, 4, 3, and 1 into bins of capacity 10 using First Fit Decreasing (FFD). Is the result optimal?
Step 1: Compute the lower bound. The total size is 20, so you need at least 2 bins.
L=⌈7+5+4+3+110⌉=⌈2010⌉=2L = \left\lceil \frac{7+5+4+3+1}{10} \right\rceil = \left\lceil \frac{20}{10} \right\rceil = 2
Step 2: Sort the items from largest to smallest: 7, 5, 4, 3, 1. Place each one in the first bin with enough room. 7 opens Bin 1. 5 does not fit with 7, so it opens Bin 2. 4 goes in Bin 2. 3 goes in Bin 1. 1 does not fit in the full Bin 1, so it goes in Bin 2.
Bin 1: 7+3=10,Bin 2: 5+4+1=10\text{Bin 1: } 7 + 3 = 10, \qquad \text{Bin 2: } 5 + 4 + 1 = 10
Step 3: FFD used 2 bins, which equals the lower bound. No packing can use fewer, so this one is optimal.
Answer: FFD packs the items into 2 bins, {7, 3} and {5, 4, 1}. This matches the lower bound of 2, so the packing is optimal.

Why It Matters

Bin packing models loading trucks and shipping containers, cutting stock from fixed-length material, and assigning virtual machines to servers. In an algorithms course it is a standard example of an NP-hard problem where approximation algorithms are used. For instance, FFD is proven never to use more than 119OPT+69\tfrac{11}{9}\text{OPT} + \tfrac{6}{9} bins.

Common Mistakes

Mistake: Assuming a greedy method like FFD always gives the optimal number of bins.
Correction: FFD is a heuristic. With capacity 10 and items 4, 4, 3, 3, 3, 3, FFD uses 3 bins: {4, 4}, {3, 3, 3}, {3}. The optimal packing uses 2 bins: {4, 3, 3} and {4, 3, 3}. Compare your result with the lower bound LL. If they match, the packing is optimal. If they do not, the packing may or may not be optimal.

Related Terms