0/1 Knapsack (Branch & Bound)

Search the include/exclude tree for 0/1 knapsack, but compute an optimistic upper bound at each node and prune any branch that can't beat the best found.

9 min read Watch it move Build it

In 0/1 knapsack each item is taken whole or not at all — no fractions — so the easy greedy rule no longer works. Branch and bound solves it by searching a tree of *include-or-exclude* decisions, but it refuses to explore the whole tree. At every node it asks: *even in the best imaginable case, could this branch beat the best complete solution I already have?* If not, it prunes the branch unseen.

Branch: the decision tree

Order items by density (value-per-weight), then branch level by level. At level i you make two children: one that includes item i and one that excludes it. A leaf is a complete yes/no assignment to every item. Exploring all of it is 2ⁿ — which is exactly what bounding lets us avoid.

Bound: the optimistic estimate

The upper bound at a node is the most value that branch could possibly reach. Compute it the lazy, optimistic way: take the value locked in so far, then fill the remaining capacity with fractions of the best remaining items — i.e. solve the *fractional* relaxation. Because fractions can only help, no real 0/1 completion of this branch can exceed that number.

Prune when optimism isn't enough

Keep the best *complete* value found so far (best). If a node's optimistic upper bound is ≤ best, then nothing inside that branch can improve on what you already hold — so abandon it without expanding a single child.

Worked example

Capacity = 10. Items, already sorted by density: I1(value 60, weight 2), I2(value 100, weight 4), I3(value 120, weight 6).

root upper bound (fractional fill of capacity 10):
  take I1 (w2,v60), I2 (w4,v100), then 4/6 of I3 = 80
  -> UB = 240   (optimistic ceiling)

best real 0/1 solutions:
  I1 + I2 = w6,  v160   (I3 won't fit in the leftover 4)
  I1 + I3 = w8,  v180
  I2 + I3 = w10, v220   <- optimal

any node whose UB <= 220 once 220 is found is pruned.

The optimal 220 comes from I2 + I3, exactly filling the bag. Notice the root bound of 240 is loose — it allowed a fraction of I3 that the 0/1 rules forbid — but that's fine: a bound only has to be *optimistic*, never exact, to safely prune.

A bad bound only costs speed, not correctness

The upper bound must never *under*-estimate the true best of a branch, or you might prune the optimum. Over-estimating is always safe — it just prunes less aggressively. The fractional relaxation is popular precisely because it's a quick, never-too-low estimate.

OperationTimeSpace

Worst case · no branch prunes — full treeO(2^n)O(n)

Bound per node · fractional fill of remaining itemsO(n)O(1)

In practice · pruning skips most of the tree≪ 2^nO(n)

Check yourself

When does branch and bound prune a node in the 0/1 knapsack tree?