Introduction

You're packing a bag for a trip and it can only hold so much weight. Every item is worth something to you, but you can't take them all. Which ones do you pick to get the most value without going over the limit?

That's the knapsack problem, and the same question appears far from any backpack: a budget that can fund only some projects, a truck that can carry only so much cargo, an ad slot that can show only a few items. In each case you choose a subset of things, each with a "cost" (weight) and a "benefit" (value), to maximize benefit without exceeding a fixed capacity.

It sounds like something you could eyeball. But as the list of items grows, the number of possible combinations explodes — and the obvious shortcuts can quietly leave value on the table.

The Greedy Approach

The natural instinct is to be greedy about efficiency: rank items by their value-to-weight ratio — the most "bang per kilo" — and keep adding the best one that still fits.

It's a great instinct, and for some versions of the problem it's exactly right. If you're allowed to take fractions of items (half a bag of coffee, a third of a gold bar), greedy by ratio is provably optimal — this is the fractional knapsack.

But real items are usually all-or-nothing: you take the whole laptop or none of it. That's the 0/1 knapsack, and there, the greedy ratio can betray you.

Try It Yourself

Here's a classic trap. The bag holds 50 kg. The greedy method grabs the lightest, most efficient items first — but that fills the bag with small items and blocks a better heavyweight combination.

Pick items to load the bag below (click to add or remove). Try to beat the bag's capacity and maximize value. Then press Greedy to see what the value-to-weight strategy chooses, and Optimal to see the true best — found by dynamic programming, which quietly considers every worthwhile combination.

<p class="hint">The bag holds <b>50&nbsp;kg</b>. Click items to put them in or take them out. Get the <b>most total value</b> without going over the weight limit. Then compare with <b>Greedy</b> (best value-per-kg first) and the true <b>Optimal</b>.</p>
<div class="meter">
  <div class="meter-row"><span>Weight</span><span id="wlabel">0 / 50 kg</span></div>
  <div class="bar"><div id="fill" class="fill"></div></div>
  <div class="value">Value in bag: <b id="vlabel">0</b> &nbsp;·&nbsp; Best possible: <b id="opt">–</b></div>
</div>
<div id="items" class="items"></div>
<div class="bar-btns">
  <button id="greedy" type="button">Greedy</button>
  <button id="optimal" type="button">Optimal</button>
  <button id="reset" type="button" class="ghost">Reset</button>
</div>
<p id="status" class="status"></p>

* { 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; }
.meter { margin-bottom: .7rem; }
.meter-row { display: flex; justify-content: space-between; font-size: .85rem; font-weight: 600; color: #555; }
.bar { height: 14px; background: #eee; border-radius: 7px; overflow: hidden; margin: .2rem 0; }
.fill { height: 100%; width: 0; background: #2a9d8f; transition: width .15s, background .15s; }
.fill.over { background: #e63946; }
.value { font-size: .9rem; }
.items { display: grid; grid-template-columns: repeat(auto-fill, minmax(120px, 1fr)); gap: .5rem; }
.item { border: 2px solid #ddd; border-radius: 10px; padding: .5rem .6rem; cursor: pointer; background: #fff; transition: all .12s; user-select: none; }
.item:hover { border-color: #999; }
.item.in { border-color: #2a9d8f; background: #e7f6f3; box-shadow: 0 2px 8px rgba(42,157,143,.2); }
.item .name { font-weight: 700; font-size: .95rem; margin-bottom: .25rem; }
.item .stat { font-size: .8rem; color: #555; }
.item .ratio { font-size: .72rem; color: #888; margin-top: .15rem; }
.bar-btns { display: flex; gap: .5rem; margin: .7rem 0 .2rem; 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; }
.status { font-size: .95rem; font-weight: 600; min-height: 1.3em; margin: .3rem 0 0; line-height: 1.4; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c0392b; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// 0/1 knapsack. Greedy-by-ratio fills the bag with light, efficient items and misses the better heavyweight combination that dynamic programming finds.
const CAP = 50;
const ITEMS = [
  { name: 'Item 1', w: 10, v: 60 },
  { name: 'Item 2', w: 20, v: 100 },
  { name: 'Item 3', w: 30, v: 120 },
  { name: 'Item 4', w: 40, v: 140 },
];
const inBag = ITEMS.map(() => false);

// Optimal value via dynamic programming (also returns which items).
function solveOptimal() {
  const n = ITEMS.length;
  const dp = Array.from({ length: n + 1 }, () => new Array(CAP + 1).fill(0));
  for (let i = 1; i <= n; i++) {
    const { w, v } = ITEMS[i - 1];
    for (let c = 0; c <= CAP; c++) {
      dp[i][c] = dp[i - 1][c];
      if (w <= c) dp[i][c] = Math.max(dp[i][c], dp[i - 1][c - w] + v);
    }
  }
  const pick = ITEMS.map(() => false);
  let c = CAP;
  for (let i = n; i >= 1; i--) {
    if (dp[i][c] !== dp[i - 1][c]) { pick[i - 1] = true; c -= ITEMS[i - 1].w; }
  }
  return { value: dp[n][CAP], pick };
}
const OPT = solveOptimal();

function totals() {
  let w = 0, v = 0;
  ITEMS.forEach((it, i) => { if (inBag[i]) { w += it.w; v += it.v; } });
  return { w, v };
}

function buildItems() {
  const box = document.getElementById('items');
  box.innerHTML = '';
  ITEMS.forEach((it, i) => {
    const el = document.createElement('div');
    el.className = 'item';
    el.innerHTML =
      fmt('<div class="name">%name%</div><div class="stat">⚖️ %w% kg · 💎 %v%</div><div class="ratio">%v2% value/kg</div>', { name: it.name, w: it.w, v: it.v, v2: (it.v / it.w).toFixed(1) });
    el.addEventListener('click', () => { inBag[i] = !inBag[i]; render(); });
    box.appendChild(el);
  });
}

function render() {
  const { w, v } = totals();
  ITEMS.forEach((it, i) =>
    document.getElementById('items').children[i].classList.toggle('in', inBag[i]));
  document.getElementById('wlabel').textContent = `${w} / ${CAP} kg`;
  document.getElementById('vlabel').textContent = v;
  document.getElementById('opt').textContent = OPT.value;
  const fill = document.getElementById('fill');
  fill.style.width = Math.min(w / CAP, 1) * 100 + '%';
  fill.classList.toggle('over', w > CAP);
  const st = document.getElementById('status');
  st.className = 'status';
  if (w > CAP) {
    st.textContent = fmt('Over the limit by %v% kg — take something out.', { v: w - CAP });
    st.classList.add('bad');
  } else if (v === OPT.value && v > 0) {
    st.textContent = fmt('Value %v% — that’s the best possible! 🎉', { v: v });
    st.classList.add('ok');
  } else if (v > 0) {
    st.textContent = fmt('Value %v%, weight %w% kg. The best possible is %value%.', { v: v, w: w, value: OPT.value });
  } else {
    st.textContent = 'Empty bag — start adding items.';
  }
}

function greedy() {
  ITEMS.forEach((_, i) => inBag[i] = false);
  const order = ITEMS.map((it, i) => ({ i, r: it.v / it.w }))
    .sort((a, b) => b.r - a.r);
  let w = 0;
  for (const { i } of order) {
    if (w + ITEMS[i].w <= CAP) { inBag[i] = true; w += ITEMS[i].w; }
  }
  render();
  const { v } = totals();
  const st = document.getElementById('status');
  st.className = 'status';
  st.textContent = v === OPT.value
    ? fmt('Greedy got %v% — optimal this time.', { v: v })
    : fmt('Greedy packed value %v% — but the optimal is %value%. Greedy left %v2% behind.', { v: v, value: OPT.value, v2: OPT.value - v });
  st.classList.add(v === OPT.value ? 'ok' : 'bad');
  console.log(fmt('Greedy value %v% (weight %w%) vs optimal %value%', { v: v, w: w, value: OPT.value }));
}

function optimal() {
  ITEMS.forEach((_, i) => inBag[i] = OPT.pick[i]);
  render();
  const st = document.getElementById('status');
  st.className = 'status ok';
  st.textContent = fmt('Optimal: value %value%, found by dynamic programming.', { value: OPT.value });
}

document.getElementById('greedy').addEventListener('click', greedy);
document.getElementById('optimal').addEventListener('click', optimal);
document.getElementById('reset').addEventListener('click', () => { ITEMS.forEach((_, i) => inBag[i] = false); render(); });

buildItems();
render();
Result
Console

You'll find the greedy bag is lighter and feels efficient, yet the optimal bag is worth more. Being locally efficient isn't the same as being globally best.

The Real Complexity

So how hard is knapsack?

  • Checking a packing is trivial: add up the weights and values, confirm you're under capacity.
  • The fractional version is easy — greedy by ratio solves it exactly, fast.
  • The 0/1 version is NP-hard. Trying every subset of n items means 2n2^{n} possibilities — hopeless beyond a few dozen items.
  • Dynamic programming solves 0/1 knapsack in O(n × capacity). That looks fast, but it's pseudo-polynomial: the cost scales with the numeric capacity, not the number of digits. A capacity in the billions makes the table enormous.
  • In practice we lean on approximation schemes (FPTAS) that get within any chosen percentage of optimal, quickly.

Knapsack is a cousin of Subset Sum and the Coin Change problem — small, friendly-looking problems that all sit right on the boundary of intractability.

Where It Matters

Any time you must choose a subset of things under a fixed limit, you're solving a knapsack:

  • Budgeting and project selection: fund the mix of projects with the most impact for a fixed budget.
  • Cargo and logistics: load a truck, ship, or plane for maximum value within a weight limit.
  • Cloud and computing: pack tasks onto a server's memory or CPU to maximize throughput.
  • Finance: assemble a portfolio of assets under a capital constraint.
  • Cryptography: early public-key systems (the Merkle–Hellman cryptosystem) were built on the hardness of knapsack-style problems.

The same trio returns everywhere: greedy is fast and often good, dynamic programming is exact but costly, and approximations bridge the gap when the numbers get big.

Conclusion

Packing a bag is the kind of decision we make without thinking — yet it captures a deep computational divide. Allow fractions and a simple greedy rule is perfect. Force all-or-nothing choices and the very same problem turns NP-hard, with the greedy shortcut quietly losing value.

That gap between fractional (easy) and 0/1 (hard) is the heart of the knapsack problem, and a recurring theme on this site: a tiny change in the rules can move a problem from trivial to intractable. The next time you decide what to leave behind, you're playing one of computer science's most studied games.

Share this article

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

Comments

Loading comments...

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