Introduction

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 First-Fit Method

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.

Pack the Bins

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">Each bin holds <b>10</b> units. Pack all the items into as <b>few bins</b> as possible. Click an item to pick it up, then click a bin to drop it in (it won’t fit if there’s no room). Click an item inside a bin to take it back. Or press <b>Auto-pack</b> to watch the First-Fit-Decreasing method do it.</p>
<div class="tray-label">Items to pack:</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">Auto-pack (First-Fit-Decreasing)</button>
  <button id="reset" type="button" class="ghost">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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Bin packing: fit items of given sizes into the fewest bins of capacity CAP.
// Greedy First-Fit-Decreasing is fast and good; the true minimum is NP-hard.
const CAP = 10;
const NBINS = 5;
const COLORS = ['#e63946', '#2a9d8f', '#457b9d', '#e9c46a', '#8e7dbe', '#e07a5f', '#3d8361', '#c77dff'];
const ITEMS = [7, 6, 5, 4, 4, 3, 3, 2].map((size, id) => ({ id, size, bin: -1 }));
let selected = null;

const load = b => ITEMS.filter(it => it.bin === b).reduce((s, it) => s + it.size, 0);
const binsUsed = () => new Set(ITEMS.filter(it => it.bin >= 0).map(it => it.bin)).size;
const lowerBound = () => Math.ceil(ITEMS.reduce((s, it) => s + it.size, 0) / CAP);

function makeItemEl(it, inBin) {
  const el = document.createElement('div');
  el.className = 'item' + (selected === it.id && !inBin ? ' sel' : '');
  el.style.background = COLORS[it.id % COLORS.length];
  el.textContent = it.size;
  if (inBin) {
    el.className = 'seg';
    el.style.width = (it.size / CAP * 100) + '%';
    el.title = 'Click to remove';
    el.addEventListener('click', e => { e.stopPropagation(); it.bin = -1; selected = null; render(); });
  } else {
    el.style.width = Math.max(it.size * 9, 28) + 'px';
    el.addEventListener('click', () => { selected = (selected === it.id ? null : it.id); render(); });
  }
  return el;
}

function render() {
  const tray = document.getElementById('tray');
  tray.innerHTML = '';
  ITEMS.filter(it => it.bin === -1).forEach(it => tray.appendChild(makeItemEl(it, false)));
  if (!tray.children.length) tray.innerHTML = '<span style="color:#888;font-size:.85rem">All items packed.</span>';

  const bins = document.getElementById('bins');
  bins.innerHTML = '';
  for (let b = 0; b < NBINS; b++) {
    const used = load(b);
    const wrap = document.createElement('div');
    wrap.className = 'bin' + (used > 0 ? ' used' : '');
    wrap.innerHTML = fmt('<div class="blabel">Bin %v%: %used%/%CAP%</div>', { v: b + 1, used: used, CAP: CAP });
    const track = document.createElement('div');
    track.className = 'track';
    ITEMS.filter(it => it.bin === b).forEach(it => track.appendChild(makeItemEl(it, true)));
    wrap.appendChild(track);
    wrap.addEventListener('click', () => placeInBin(b));
    bins.appendChild(wrap);
  }

  const st = document.getElementById('status');
  const lb = lowerBound();
  const allPacked = ITEMS.every(it => it.bin >= 0);
  const used = binsUsed();
  if (!allPacked) {
    st.className = 'status';
    st.textContent = fmt('Bins used: %used%. Pack everything — the fewest possible here is %lb%.', { used: used, lb: lb });
  } else if (used <= lb) {
    st.className = 'status ok';
    st.textContent = fmt('All packed in %used% bins — that’s the minimum possible! 🎉', { used: used });
  } else {
    st.className = 'status bad';
    st.textContent = fmt('All packed in %used% bins. Can you do it in %lb%?', { used: used, lb: lb });
  }
}

function placeInBin(b) {
  if (selected === null) return;
  const it = ITEMS[selected];
  if (load(b) + it.size > CAP) {
    const st = document.getElementById('status');
    st.className = 'status bad';
    st.textContent = fmt('Item %size% doesn’t fit in Bin %v% (only %v2% left).', { size: it.size, v: b + 1, v2: CAP - load(b) });
    return;
  }
  it.bin = b; selected = null; render();
}

function firstFitDecreasing() {
  ITEMS.forEach(it => it.bin = -1);
  [...ITEMS].sort((a, b) => b.size - a.size).forEach(it => {
    for (let b = 0; b < NBINS; b++) {
      if (load(b) + it.size <= CAP) { it.bin = b; break; }
    }
  });
  selected = null;
  render();
  console.log(fmt('First-Fit-Decreasing used %binsUsed% bins (lower bound %lowerBound%).', { binsUsed: binsUsed(), lowerBound: lowerBound() }));
}

document.getElementById('ffd').addEventListener('click', firstFitDecreasing);
document.getElementById('reset').addEventListener('click', () => { ITEMS.forEach(it => it.bin = -1); selected = null; render(); });
render();
Result
Console

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.

The Real Complexity

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.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/bin-packing/Content licensed under CC BY-NC 4.0.