Bin Packing

You're moving house, and you have a pile of things and a stack of identical boxes. Each box holds only so much. How do you pack everything using as few boxes as possible?

That's the bin packing problem: given items of various sizes and bins of a fixed capacity, fit all the items into the fewest bins. It's the mirror image of the knapsack problem — instead of choosing what to leave out of one container, you must fit everything into as few containers as you can.

It feels like something you'd just eyeball. And for a few items, you can. But the moment the pile grows, finding the truly tightest packing becomes one of the classic hard problems of computer science.

The natural strategy is First-Fit: take the items one by one, and drop each into the first bin that still has room. Only when nothing fits do you open a new bin.

First-Fit is fast and never wastes a bin needlessly, but its result depends on the order the items arrive in. A famously better twist is First-Fit-Decreasing (FFD): sort the items from largest to smallest first, then run First-Fit. Big items get placed while bins are empty, and the small ones trickle into the gaps.

FFD is remarkably good — it's guaranteed to use at most about 11/9 of the optimal number of bins, plus a small constant. For a method this simple, that's close. But "close" isn't "perfect", and perfect is where the trouble begins.

Try it. Below are eight items and a row of bins, each holding 10 units. Pick an item, drop it in a bin, and try to fit everything into the fewest bins.

Notice how the choices interact: a single misplaced big item can force an extra bin you didn't need. There's a hint at the bottom — the lower bound, the fewest bins that could possibly work (just the total size divided by the bin capacity, rounded up). Hitting it isn't always possible, and even when it is, finding the arrangement can take real effort.

<p class="hint">{{hint}}</p>
<div class="tray-label">{{tray_label}}</div>
<div id="tray" class="tray"></div>
<div id="bins" class="bins"></div>
<p id="status" class="status"></p>
<div class="bar-btns">
  <button id="ffd" type="button">{{btn_autopack}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
.tray-label { font-size: .82rem; font-weight: 600; color: #555; margin-bottom: .25rem; }
.tray { display: flex; flex-wrap: wrap; gap: .4rem; min-height: 40px; padding: .4rem; background: #f4f4f4; border-radius: 8px; margin-bottom: .7rem; }
.item { height: 34px; border-radius: 6px; border: 2px solid rgba(0,0,0,.15); color: #fff; font: 700 13px system-ui; display: flex; align-items: center; justify-content: center; cursor: pointer; user-select: none; transition: transform .1s, box-shadow .1s; }
.item.sel { outline: 3px solid #111; outline-offset: 1px; transform: translateY(-2px); }
.bins { display: flex; flex-direction: column; gap: .45rem; }
.bin { cursor: pointer; }
.bin .blabel { font-size: .8rem; font-weight: 600; color: #555; margin-bottom: .15rem; }
.bin .track { display: flex; height: 34px; background: #eee; border: 2px dashed #ccc; border-radius: 8px; overflow: hidden; }
.bin.used .track { border-style: solid; border-color: #bbb; }
.seg { height: 100%; display: flex; align-items: center; justify-content: center; color: #fff; font: 700 12px system-ui; border-right: 1px solid rgba(255,255,255,.5); cursor: pointer; }
.status { font-size: 1rem; font-weight: 700; min-height: 1.3em; margin: .5rem 0; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c0392b; }
.bar-btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #457b9d; background: #457b9d; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #457b9d; }

// Code not found

When you're stuck, press Auto-pack to watch First-Fit-Decreasing. It's fast and usually excellent — but remember, "usually excellent" is a heuristic, not a guarantee of the true minimum.

How hard is bin packing, really?

• Checking a packing is trivial: confirm no bin is over capacity and count the bins.
• Finding the fewest bins is NP-hard. Even the yes/no question "can these items fit in k bins?" is NP-complete — it contains Subset Sum-style difficulty.
• But approximations are excellent. First-Fit-Decreasing stays within ~11/9 of optimal; even better schemes get within any chosen percentage. This is the happy side of bin packing: provably near-optimal answers, fast.
• Online is harder still. If items arrive one at a time and must be placed immediately — no peeking ahead — you can't sort them first, and the best possible guarantee gets weaker.

So bin packing lives in a comfortable middle: optimal is intractable, but "almost optimal" is cheap and reliable — which is exactly why it works so well in the real world.

Bin packing is everywhere goods, data, or time must be squeezed into fixed-size slots:

• Shipping and logistics: loading the fewest trucks, containers, or pallets — every empty gap is wasted fuel and money.
• Cloud computing: packing virtual machines onto the fewest physical servers (and powering the rest down) is a multi-billion-dollar bin packing problem.
• Manufacturing and cutting: fitting parts onto sheets of metal, wood, or fabric to minimize scrap — closely related to its cousin, the cutting-stock problem.
• Media and advertising: filling broadcast breaks or bandwidth with the fewest gaps.
• Storage and memory: allocating files or data blocks to minimize wasted space.

Shaving even a few percent off the bins used translates into enormous savings — which is why "almost optimal, instantly" is one of computing's most valuable bargains.

Packing boxes is the kind of task you'd never call hard — until you insist on the fewest boxes, every time, guaranteed. That guarantee is NP-hard. And yet bin packing is also one of the most encouraging problems on this site: a dead-simple rule like First-Fit-Decreasing gets you provably close to perfect, in an instant.

That's the recurring trade-off of the field in miniature. The exact optimum hides behind a wall of intractability, but a clever, humble heuristic walks right up to that wall and gets almost everything we wanted. For a problem that quietly runs the world's shipping and data centers, "almost perfect, instantly" turns out to be more than enough.