Introduction

Imagine a long roll of fabric, paper, or sheet metal. Its width is fixed, but its length is as long as you need. You have a pile of rectangular pieces to cut from it, and every piece must fit without overlapping or being rotated past the rules. The question is simple to state: how do you arrange them so the roll you use is as short as possible?

That is the strip packing problem. You are not allowed to make the strip wider — only longer — so all the cleverness goes into how you nest the rectangles side by side and stack them up. Waste any space and you waste material; in a factory that runs all day, those gaps cost real money.

It looks like a tidy game of Tetris with no time pressure. And yet, finding the genuinely shortest arrangement is one of the hardest kinds of problems in all of computer science. Strip packing is the two-dimensional cousin of bin packing — and it inherits the same intractability.

Try It: Shelf vs. Tight Packing

Below is a strip of fixed width and a fixed set of rectangles. Two strategies place the same pieces. The shelf heuristic is the simple, fast one: lay pieces left to right on a row, and when the next piece won't fit, start a new shelf on top. The tight packing slides each piece down and left into the lowest gap it can reach.

<p class="hint">A strip of <b>fixed width</b> holds these rectangles. Pack them two ways and compare the total <b>height</b> used. Checking a layout is instant; finding the truly shortest one is NP-hard.</p>
<div class="stage">
  <div class="panel">
    <div class="cap">Shelf heuristic <span id="h-shelf" class="badge">–</span></div>
    <canvas id="shelf" width="220" height="320"></canvas>
  </div>
  <div class="panel">
    <div class="cap">Tight packing <span id="h-tight" class="badge">–</span></div>
    <canvas id="tight" width="220" height="320"></canvas>
  </div>
</div>
<div class="status" id="status">Press a button to pack the rectangles.</div>
<div class="btns">
  <button id="run-shelf" type="button">Pack: shelf</button>
  <button id="run-tight" type="button">Pack: tight</button>
  <button id="run-both" type="button">Pack both</button>
  <button id="shuffle" type="button" class="ghost">New rectangles</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 .7rem; line-height: 1.45; }
.stage { display: flex; gap: 1.2rem; flex-wrap: wrap; }
.panel { text-align: center; }
.cap { font: 600 14px system-ui, sans-serif; color: #1d3557; margin-bottom: .35rem; }
.badge { display: inline-block; min-width: 2.4em; padding: .05rem .45rem; margin-left: .3rem;
         background: #e8eef3; color: #1d3557; border-radius: 6px; font-weight: 700; }
canvas { background: #f4f6f8; border: 2px solid #1d3557; border-radius: 6px; }
.status { font-size: 1rem; font-weight: 600; margin: .7rem 0 .5rem; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Strip packing: rectangles of a fixed-width strip, minimize total height used.
    // We compare two heuristics on the SAME pieces:
    //   shelf  - next-fit shelf: fill a row left-to-right; new row when a piece won't fit.
    //   tight  - bottom-left / skyline: drop each piece into the lowest feasible x.
    // Finding the true minimum height is NP-hard (it contains bin packing).
const W = 10;                 // strip width in grid units
const SCALE = 22;             // px per unit
const PAD = 4;
const COLORS = ['#457b9d','#e63946','#2a9d8f','#e9c46a','#8d6cab','#f4a261','#3d5a80','#9d4edd'];
let pieces = [];

function makePieces(){
  // widths in [2..W], heights in [1..4]; total area kept moderate so both fit.
  const rng = () => Math.random();
  const n = 8;
  pieces = [];
  for(let i=0;i<n;i++){
    const w = 2 + Math.floor(rng()*(W-1));   // 2..W
    const h = 1 + Math.floor(rng()*4);       // 1..4
    pieces.push({ w: Math.min(w,W), h, c: COLORS[i%COLORS.length] });
  }
}

// ── Shelf (next-fit) ──────────────────────────────────────────────────────
function packShelf(ps){
  const out = []; let x=0, shelfY=0, shelfH=0;
  for(const p of ps){
    if(x + p.w > W){ shelfY += shelfH; x = 0; shelfH = 0; }   // new shelf
    out.push({ ...p, x, y: shelfY });
    x += p.w; shelfH = Math.max(shelfH, p.h);
  }
  const height = shelfY + shelfH;
  return { placed: out, height };
}

// ── Tight (bottom-left over a skyline) ──────────────────────────────────────
// skyline[x] = current filled height of column x. Place each piece at the x
    // (0..W-w) whose max column-height over its width is smallest (ties: leftmost).
function packTight(ps){
  const sky = new Array(W).fill(0);
  const out = [];
  for(const p of ps){
    let bestX = 0, bestY = Infinity;
    for(let x=0; x + p.w <= W; x++){
      let y = 0;
      for(let k=x; k<x+p.w; k++) y = Math.max(y, sky[k]);
      if(y < bestY){ bestY = y; bestX = x; }
    }
    out.push({ ...p, x: bestX, y: bestY });
    for(let k=bestX; k<bestX+p.w; k++) sky[k] = bestY + p.h;
  }
  const height = Math.max(...sky);
  return { placed: out, height };
}

function draw(id, res){
  const cv = document.getElementById(id), g = cv.getContext('2d');
  g.clearRect(0,0,cv.width,cv.height);
  for(const r of res.placed){
    const px = PAD + r.x*SCALE, py = PAD + r.y*SCALE;
    g.fillStyle = r.c;
    g.fillRect(px, py, r.w*SCALE-1, r.h*SCALE-1);
    g.strokeStyle = 'rgba(255,255,255,.7)'; g.lineWidth = 1;
    g.strokeRect(px+0.5, py+0.5, r.w*SCALE-2, r.h*SCALE-2);
  }
  // height line
  const hy = PAD + res.height*SCALE;
  g.strokeStyle = '#c92f3c'; g.setLineDash([5,3]); g.lineWidth = 1.5;
  g.beginPath(); g.moveTo(0, hy); g.lineTo(cv.width, hy); g.stroke();
  g.setLineDash([]);
}

let lastShelf=null, lastTight=null;
function runShelf(){ lastShelf = packShelf(pieces); draw('shelf', lastShelf);
  document.getElementById('h-shelf').textContent = lastShelf.height; report(); }
function runTight(){ lastTight = packTight(pieces); draw('tight', lastTight);
  document.getElementById('h-tight').textContent = lastTight.height; report(); }
function report(){
  const s = document.getElementById('status');
  if(lastShelf && lastTight){
    const saved = lastShelf.height - lastTight.height;
    if(saved > 0){
      s.textContent = fmt('Tight packing saves %saved% units of height — same pieces, less strip.', { saved: saved });
      s.className = 'status ok';
    } else if(saved === 0){
      s.textContent = 'This time both used the same height. Try new rectangles.';
      s.className = 'status';
    } else {
      s.textContent = 'This time the simple shelf got lucky and packed lower — neither greedy method is guaranteed optimal!';
      s.className = 'status';
    }
  } else { s.textContent = 'Packed. Run the other method to compare.'; s.className='status'; }
}
function reset(){
  makePieces(); lastShelf=lastTight=null;
  ['shelf','tight'].forEach(id=>{ const cv=document.getElementById(id);
    cv.getContext('2d').clearRect(0,0,cv.width,cv.height); });
  document.getElementById('h-shelf').textContent='–';
  document.getElementById('h-tight').textContent='–';
  document.getElementById('status').textContent='New rectangles. Press a button to pack.';
  document.getElementById('status').className='status';
}
document.getElementById('run-shelf').addEventListener('click', runShelf);
document.getElementById('run-tight').addEventListener('click', runTight);
document.getElementById('run-both').addEventListener('click', ()=>{ runShelf(); runTight(); });
document.getElementById('shuffle').addEventListener('click', reset);
makePieces();
Result
Console

Press the buttons and watch the total height each method needs. The shelf method is quick and easy to reason about, but it leaves ragged gaps above short pieces. The tighter packing reuses that wasted space and ends up lower. Now imagine dozens of pieces in dozens of sizes — the number of possible arrangements explodes, and no fast method is guaranteed to find the true minimum.

The Real Complexity

How hard is it to find the shortest possible strip? Genuinely hard.

  • Checking a proposed layout is easy: confirm no two rectangles overlap, none spills past the fixed width, and read off the total height.
  • Searching for the best layout is the trouble. Each rectangle can go in many positions; the arrangements multiply combinatorially, and there is no known shortcut.
  • It's NP-hard. Strip packing contains bin packing as a special case — make every rectangle the same height, and packing them into minimum strip length is exactly bin-packing items into bins. Since bin packing is strongly NP-hard, so is strip packing, and its decision version ("does a packing of height at most H exist?") is NP-complete.
  • No exact polynomial algorithm is known, and finding one would settle P vs NP. In practice we use approximation algorithms with provable guarantees: classic results give arrangements within a constant factor of optimal, and the best known asymptotic ratio for the offline problem approaches 5/3.

So the comfortable feeling that "you could just shuffle the pieces a bit" is an illusion. Past a handful of rectangles, "shuffle until perfect" means searching an exponential haystack — the same wall behind every NP-hard problem.

Where It Matters

"Fit these shapes into a fixed-width space using as little length as possible" describes a startling number of real jobs:

  • Cutting stock: textile, paper, glass and metal are sold in fixed-width rolls or sheets; minimizing length cut is minimizing waste. This is the industrial heart of cutting stock.
  • Chip and PCB layout: placing rectangular blocks on silicon of fixed width while shrinking the chip's height is a strip-packing problem with billions of dollars riding on the gaps.
  • Advertising and image layout: fitting banners or photos of various sizes into a fixed-width column with minimal scroll length is the same shape of problem.
  • Scheduling: a rectangle's width can be "machines used" and its height "time taken" — packing them tightly is scheduling parallel jobs to finish as early as possible.

Learn why strip packing is hard and you have met a whole family of placement and scheduling problems that quietly run modern industry.

Conclusion

Strip packing hides a familiar twist: it is effortless to check a layout and brutally hard to find the best one. Because it contains bin packing, it is NP-hard, and a fast exact algorithm would topple P vs NP. So in the real world we settle for clever heuristics and approximations that come close enough.

The next time you watch a cutting machine nest shapes onto a roll, or a layout engine arrange tiles on a page, remember: it is not chasing perfection. It is making peace with an intractable problem — and doing a remarkably good job of getting close.

Share this article

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

Comments

Loading comments...

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