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 and item sizes with , find a partition of into the fewest sets such that for every . The minimum is written . The decision version ("can the items fit in bins?") is NP-complete, so no polynomial-time algorithm is known that always finds .
Key Formula
Where:
- = lower bound on the number of bins needed
- = size of item i
- = capacity of each bin
- = 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.
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.
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 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 . If they match, the packing is optimal. If they do not, the packing may or may not be optimal.
