Bin packing calculator: first fit and first fit decreasing

What this calculator does

Bin packing is the problem of fitting a list of items into as few fixed-size containers as possible. It turns up whenever something has to be divided into equal-capacity units: shipping cartons, virtual machines on servers, adverts into a commercial break, cutting lengths from stock timber.

It is also NP-hard, so for any list of realistic size nobody computes the true optimum. What gets used instead are heuristics, and the two classics are here. First fit walks the list in order and drops each item into the first bin with room. First fit decreasing sorts the items largest first and then does exactly the same thing. The sort is the whole difference, and it is usually worth a bin or two.

The formula

Formulafirst fit places each item in the first bin it fits; first fit decreasing sorts largest first and does the same. The floor is ceil(total size ÷ bin capacity)

The lower bound is the one thing that is certain: you cannot use fewer bins than total size ÷ capacity, rounded up, because the bins cannot hold more than their capacity. Whether that bound is reachable is a separate and much harder question, so the figure here is a floor rather than the answer. First fit decreasing is guaranteed to come within 11/9 of the true optimum plus a small constant, which in practice usually means it lands on the optimum or one above it.

Term	Meaning
First fit	Place each item, in the order given, into the first bin that has room. An online method: it never looks ahead.
First fit decreasing	Sort the items largest first, then run first fit. An offline method: it needs the whole list up front.
Lower bound	Total size divided by capacity, rounded up. Not necessarily achievable.
Average fill	How full the bins are on average. The complement of wasted space.

The inputs explained

Field	What to enter
Item sizes	Item sizes separated by commas or spaces. Any item larger than a bin makes the problem impossible, and the calculator will say so.
Bin capacity	The capacity of one bin. Every bin is the same size.

When to use it

Seeing what the sort buys you

The default list needs four bins by first fit and three by first fit decreasing, from exactly the same items. The large items are what cause trouble, and placing them first means the small ones can fill the gaps afterwards rather than being stranded.

Cutting stock or loading pallets

Lengths cut from standard stock, or cartons loaded to a weight limit, are the same arithmetic. The spare column in the table is the offcut, and the average fill is the yield.

Knowing when you are already optimal

If the bins come out full and the count matches the lower bound, you are done and no cleverer method can help. That is worth checking before reaching for anything more sophisticated.

Worked examples

Every figure in the tables below is produced by this page’s own calculator at build time, so the numbers and the tool always agree. Select any row to load that scenario.

How much does the bin size change things?

The same items throughout, into bins of different capacity.

Seven items: 20, 50, 40, 70, 10, 30, 80

Bin capacity	Bins used, first fit decreasing	Bins used, first fit in order	Lower bound on bins
80	4	4	4
100	3	4	3
120	3	3	3
150	2	2	2
200	2	2	2

At a capacity of 100 the two methods disagree, with first fit needing four bins and first fit decreasing three. At most other capacities they agree. That is the usual pattern: the sort matters at the awkward sizes where a large item can strand a bin, and makes no difference when the items happen to fit easily either way.

What does the heuristic cost against the floor?

Different item lists, from easy to awkward.

Bin capacity fixed at 100

Items	Bins used, first fit decreasing	Lower bound on bins	Average fill
50, 50, 50, 50	2	2	100.0%
20, 50, 40, 70, 10, 30…	3	3	100.0%
51, 28, 28, 28, 27, 26	3	2	62.7%
60, 60, 60, 40, 40, 40	3	3	100.0%
99, 97, 94, 93, 91, 90	6	6	94.0%

The third row is the interesting one: 51 plus three 28s is 135, so the 51 can only share with one other item, and the four remaining items total 109 and need two more bins. The lower bound says two, the honest answer is three, and first fit decreasing finds three. The last row is the opposite case, where every item is nearly a full bin and no packing can help at all.

Questions

Why not just compute the optimal packing?

Because bin packing is NP-hard, so the only known exact methods take time that grows faster than any polynomial. For a handful of items you could brute-force it; for a realistic list nobody does.

Is first fit decreasing always better than first fit?

Almost always, and never meaningfully worse in practice, but it needs the whole list in advance. If items arrive one at a time and must be placed immediately, you cannot sort, which is the online version of the problem.

How good is first fit decreasing?

It is guaranteed to use at most 11/9 of the optimal number of bins plus a small constant. In ordinary cases it usually lands on the optimum or one bin above it.

Why does the lower bound sometimes look unreachable?

Because it only accounts for total volume, not shape. Six items of size 51 total 306, so the bound says four bins of capacity 100, but no two of them fit together, so the real answer is six.

What did AI contribute here?

In 2023 DeepMind's FunSearch searched for better heuristics for the online version, where items arrive one at a time, and found rules that beat the standard ones on well-studied input distributions. It did not solve bin packing, it found better rules of thumb.

For the counting that sits underneath, see permutations and combinations, and for the related sorting question see sorting comparisons. The story of the search that found better online rules is in the piece on FunSearch and bin packing.