The Knapsack Problem

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 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.

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">{{hint}}</p>
<div class="meter">
  <div class="meter-row"><span>{{weight_label}}</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">{{btn_greedy}}</button>
  <button id="optimal" type="button">{{btn_optimal}}</button>
  <button id="reset" type="button" class="ghost">{{btn_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; }

// Code not found

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.

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 $2^{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.

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.

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.