AlgoPlus//branch & bound / knapsack-bb
Read the theory

0/1 Knapsack · Branch & Bound

Search include/exclude decisions, pruning any branch whose optimistic value can't win.

Best value
Nodes
Your items (value/weight, comma-separated)
Legend
Evaluating
Live node
Pruned
New best
AI Tutor Workspace
In a nutshell
Branch and bound solves the 0/1 knapsack — each item taken whole or not at all — by exploring a tree of include/exclude decisions, but it doesn't expand every branch. At each node it computes an upper bound: the most value that branch could possibly reach, estimated by optimistically filling the leftover capacity with fractions of the best remaining items. If that optimistic bound can't beat the best complete solution found so far, the whole branch is pruned unseen. The worst case is still exponential, but pruning skips huge parts of the tree in practice.
Ready
Press play to begin the cinematic walkthrough.
Explore include/exclude choices, but at each node ask: even in the best case, can this branch beat what I already have? If not, cut it — no need to look inside.
Key terms
Go deeper in the lesson
Read the full theory, intuition & complexity for 0/1 Knapsack · Branch & Bound.