The bin packing problem

Moving house, you fill one box after another and wonder whether a cleverer order would have needed fewer. That is the bin packing problem, and it is famously hard: even computers find the fewest bins for large inputs only by clever search. Simple rules, though, come surprisingly close.

Bins of equal height filled with stacked coloured items of different sizes, with more items waiting above them
Bins of equal height filled with stacked coloured items of different sizes, with more items waiting above them

The problem

Given items with sizes and bins that each hold the same amount, put every item in a bin so that no bin overflows, using as few bins as possible. The sizes can stand for weights, lengths, durations or file sizes. It sounds like a puzzle for a rainy afternoon, but it is NP-hard: no method is known that finds the fewest bins quickly for every input.

Quick rules

Next fit fills one bin until the next item does not fit, then starts a new bin and never looks back. First fit keeps every bin open and puts each item in the first bin with room. Best fit puts each item in the fullest bin that still has room. All three decide at once, which is useful when the items arrive one at a time and must be placed straight away.

Sort first

Big items are the hard ones, because they need a lot of free space. Sorting the items from biggest to smallest and then using first fit or best fit puts the big items in while the bins are still empty, and fills the gaps with the small ones. First fit decreasing never uses more than 11/9 of the fewest bins, plus a constant, against 1.7 times for first fit on unsorted items.

An example

Take bins of size 10 and the items 2, 3, 2, 1, 3, 4, 5, 6, 7 and 7, which add up to 40. First fit puts 2, 3, 2 and 1 in the first bin and 3 and 4 in the second, and then 5, 6, 7 and 7 each need a bin of their own: 6 bins. Sorted biggest first, first fit decreasing makes 7 + 3, 7 + 3, 6 + 4 and 5 + 2 + 2 + 1: 4 full bins, which matches the lower bound of 40 / 10 = 4.

Finding the fewest bins

For a small number of items the exact answer can be found by dynamic programming over subsets: for each set of items, the fewest bins and the emptiest last bin that hold it, built up from the sets with one item fewer. That takes about 2ⁿ·n steps for n items. Larger instances are solved by branch and bound or integer programming, and the lower bound tells how far from the best a packing can be.

Where it is used

Loading trucks and containers, cutting pipes or paper rolls from standard lengths with as little waste as possible (the cutting stock problem), fitting virtual machines onto servers, and packing files onto disks are all bin packing problems. In two and three dimensions, with boxes instead of numbers, the problem is harder still.

Frequently asked questions

What is the difference between online and offline bin packing?

Online, each item must be placed as soon as it arrives, without knowing the rest; next fit, first fit and best fit work that way. Offline, all items are known in advance, so they can be sorted first, as first fit decreasing does.

How close does first fit decreasing get?

It uses at most 11/9 of the fewest bins plus 6/9 of a bin, a bound that György Dósa proved to be exact in 2007. On typical inputs it is usually optimal or one bin away.

Is bin packing the same as the knapsack problem?

They are related but different. Knapsack fills one bag with the most valuable items; bin packing puts every item into as few bags as possible. Exact bin packing solvers often work by solving knapsack-like problems again and again.

Why does the app allow only 12 items?

Because the exact answer looks at every set of items, and 12 items already make 4,096 sets. The quick rules would handle thousands of items, but the drawing and the comparison with the exact answer would not.

Ready to try it?

Open PictorX in your browser — no install, no credit card required to start.

Try bin packing