First-Fit Heuristic¶

Definition¶

The first-fit heuristic processes packing items in their given order. Place the current item into the first previously opened container with enough unused capacity. If no such container exists, open a new container and place the item there. Assume every item individually fits in a container.

Interpretation¶

First fit packs the items one at a time and never reconsiders a placement. Each item goes into the earliest opened container that still has room, and a new container is opened only when none has.

Three containers of capacity 50 filled by first fit: 15 and 30 in the first, 20 in the second and 35 in the third, although two containers would suffice.

The figure follows the order $15,30,20,35$ with capacity $50$ . Items $15$ and $30$ share container 1, leaving $5$ units free. The $20$ does not fit there ( $45 +$ $45+20>50$ $50$ ) and opens container 2. The $35$ fits neither container 1 ( $45 +$ $45+35>50$ $50$ ) nor container 2 ( $20 +$ $20+35>50$ $50$ ) and opens container 3. Two containers suffice for these items, so first fit is not optimal here.

Each part of the rule has a role. "First" means the earliest opened container, not the fullest or the emptiest one; another choice gives a different heuristic. Because an item is only placed where it fits, every intermediate packing respects capacity, and the assumption that each item fits into an empty container guarantees that opening a new container always works. The result depends on the item order: with the order $35,30,20,15$ the same items need only two containers.

As a heuristic for the bin packing problem, first fit gives a feasible packing and hence an upper bound on the minimum number of containers; comparing it with the total-weight lower bound shows how far from optimal it can be.

Key Results¶

Every produced packing respects capacity.
Its container count is an upper bound, not a proof of optimality.
The exercise gives this procedure without a name; first-fit is its conventional search name.

Examples¶

The illustrated order $15,30,20,35$ with capacity 50 uses three containers under first fit. Two suffice with $\{15,35\}$ and $\{30,20\}$ , so that first-fit result is not optimal. Reordering the same items as $35,30,20,15$ makes first fit use two containers here.

In the course exercise, items 1, 2, 3, and 9 fill container 1 to weight 49.
Items 6, 7, and 8 fill another container to weight 49; the full heuristic packing uses five containers.

Prerequisites¶

Bin Packing Problem

Sources¶

OR Modelling · Week 1

Aliases: first-fit algorithm, first fit

Last updated: 20 October 2026 03:02