Every other Backtracking entry on this site answers a yes-or-no (or find-one, or find-all) question: is there a valid queen placement, a valid Sudoku fill, a valid coloring, a valid tour, a subset that sums exactly, a string cut entirely into palindromes, an exact cover. A valid solution is a valid solution — none of those nine entries ever compares two solutions against each other to ask which is better. This page's question is different in kind, not just in subject: given a set of items, each with its own weight and value, and a knapsack that can carry at most a fixed total weight, which items should go in to make the total value as large as possible? The same optimization question 0/1 Knapsack already answers on this site — by filling a table bottom-up. This page answers it by searching and backtracking instead, the way Subset Sum does, extending one item at a time and abandoning a branch the instant it can't work out. What's new is why a branch gets abandoned: not because it's already broken some rule — it may still be entirely legal — but because an optimistic estimate of the best this branch could still become, computed once and cheaply, can't beat the best complete answer already in hand. Reject a queen placement and it's gone for a structural reason. Reject a knapsack branch here and it might well have led somewhere feasible — just never anywhere as good as what's already been found.
The same five fixed hiking-pack items and capacity-10 knapsack
0/1 Knapsack uses, not user-editable, same convention as
this site's other fixed-content interactive demos — reused deliberately, so the final answer here
can be checked directly against that page's own table. Before searching, the items are sorted once
by value-per-weight ratio, highest first: Stove (8/3 ≈ 2.67), Food
(9/4 = 2.25), Tent (13/6 ≈ 2.17), Rope (4/2 = 2.00), and
Water (10/5 = 2.00). Press Step or Run to watch
the search: at each node it tries including the next item (skipped outright if it
would overflow the capacity), then excluding it. Before descending into either
child, it computes a bound — the most this branch could possibly still be worth —
and compares it to the best complete value found so far. If the bound can't beat that incumbent,
the whole branch is pruned without trying anything further, even though nothing
about it was actually illegal.
The bound at any node is a classic fractional-knapsack relaxation: pretend, just for this estimate, that the remaining capacity could be topped up with a fraction of the next unconsidered item instead of only whole items. Because the items are pre-sorted by ratio, that greedy fractional fill computes the true optimal fractional-knapsack value for whatever's left — and a fractional packing can only ever be worth at least as much as the best all-or-nothing one, since every integer solution is itself one particular (all-whole-number) fractional solution. That's what makes the bound an honest upper bound rather than a guess: no integer completion of this branch can ever exceed it, so if even this optimistic number can't beat the best real answer already found, there is provably nothing left worth exploring here.
Run against this page's own five items, the search visits 18 nodes and triggers
2 prunes before settling on a best value of 22, achieved by
Stove + Rope + Water (weight 3 + 2 + 5 = 10, value
8 + 4 + 10 = 22) — computed directly from the demo's own reference implementation
below, not estimated. That's the identical 22 the
0/1 Knapsack page's dynamic-programming table finds for the
same five items and the same capacity, just reached by exploring branches instead of filling cells —
and it's a different one of that page's own two tied-optimal packs, not the same one. That page's
own Pitfalls section already found Tent + Food tied at 22 (weight
6 + 4 = 10); the two algorithms happen to land on different equally-valid witnesses for
the identical best value, exactly the kind of tie that page warned isn't ambiguous in its total but
can be ambiguous in which items get named. Plain exhaustive backtracking over these same five items —
respecting the weight cap but computing no bound and pruning nothing — visits 43
nodes to reach the same answer: the bound cuts node count by 58% here, without
changing what gets found.
function branchAndBoundKnapsack(items, capacity) {
// sort once, best value-per-weight first — this order is what makes the bound valid
const order = items.slice().sort((a, b) => (b.value / b.weight) - (a.value / a.weight));
const n = order.length;
// the most value achievable from index i onward, given usedWeight/value so far,
// if the next unconsidered item could be split fractionally to fill the rest —
// an upper bound no integer combination of these items can ever exceed
function bound(i, usedWeight, value) {
let remaining = capacity - usedWeight;
let best = value;
let j = i;
while (j < n && order[j].weight <= remaining) {
remaining -= order[j].weight;
best += order[j].value;
j++;
}
if (j < n && remaining > 0) {
best += order[j].value * (remaining / order[j].weight); // fractional slice of the next item
}
return best;
}
let bestValue = 0;
let bestChoice = [];
const chosen = [];
function explore(i, usedWeight, value) {
if (value > bestValue) { bestValue = value; bestChoice = chosen.slice(); }
if (i === n) return;
if (bound(i, usedWeight, value) <= bestValue) return; // can't beat what we already have — prune
if (usedWeight + order[i].weight <= capacity) {
chosen.push(order[i]);
explore(i + 1, usedWeight + order[i].weight, value + order[i].value);
chosen.pop(); // backtrack: undo the inclusion
}
explore(i + 1, usedWeight, value);
}
explore(0, 0, 0);
return { bestValue, bestChoice };
}The bound is only a true upper bound if the items are sorted by value-per-weight ratio —
sorting by raw value instead quietly breaks it, and can prune away the actual optimum.
Checked with a throwaway script, not reproducible on this page's own five items (both orderings
happen to land on the same total there): for items A (weight 6, value 3),
B (weight 6, value 5), C (weight 2, value 2), and D (weight
4, value 4) with capacity 6, the true best is 6, from
C + D. Sort by ratio (C, D, B, A) and the search finds it correctly. Sort
by raw value instead (B, D, A, C) and the very first bound computed after excluding
B — greedily filling the fractional estimate with D alone, since
lower-value C now sits last in line — comes out to exactly 5, tying
the incumbent B-alone solution and triggering a prune that throws away the entire
subtree C + D lives in. The search reports 5 instead of
6 — a real wrong answer, not just a slower right one, because a fractional fill
computed in the wrong item order is no longer guaranteed to dominate every integer packing of what's
left.
Updating the best-found value only at a complete leaf, instead of at every node visited,
still finds the correct optimum but prunes noticeably less. Every partial choice the search
holds — even one that hasn't decided all the items yet — is already a legal, complete-enough
knapsack packing in its own right (nothing says every item must be decided before capacity is
"used"), so it's always safe to compare it against the incumbent immediately rather than waiting
for a leaf. Not reproducible as a wrong answer on this page's own five items — both variants land on
the same 22 — but measured on a throwaway eight-item instance (capacity 15) where the
difference actually shows: comparing at every node visits 17 nodes, comparing only
at leaves visits 21, both correctly reaching the same best value. The bound's power
to prune depends entirely on how good the incumbent already is — delaying when that incumbent gets
updated delays every prune that depends on it.
Time: O(2n) in the worst case, same order as plain
backtracking — a bound only ever shrinks the constant factor by how much of the tree it actually
manages to prune, and an adversarial instance where every item shares the identical value-to-weight
ratio makes the fractional relaxation exact at every node, meaning nothing is ever eliminated before
capacity itself runs out. This page's own 18-vs-43 node comparison
above is a real, measured reduction on one instance, not a change to the underlying order.
Space: O(n) for the recursion stack and the current partial choice,
the same as every other search-and-backtrack entry on this site — the bound is computed fresh at
each node from the running totals already being tracked, never a separate table.
The same fixed-item-order plus optimistic-bound shape generalizes past knapsack to any optimization search where a cheap relaxation of the remaining subproblem can be computed — job scheduling with deadlines, the traveling salesman problem bounded by a minimum spanning tree over unvisited cities, integer programming relaxed to its continuous linear program. What's specific to this page is the particular relaxation (drop the all-or-nothing constraint) and the particular problem it bounds. This site's guide, Choosing a Backtracking Strategy, compares this entry against the other nine Backtracking entries side by side — including Dancing Links, the other entry that doesn't fit the plain reject/place/backtrack mold, for a different reason than this page does.