Branch and Bound

Why Branch and Bound Matters

Suppose you can load at most ten units of weight into a vehicle. Each optional shipment has a weight and a value, and each can be selected at most once. Trying every subset guarantees the best answer, but the number of subsets doubles with each extra shipment. A greedy choice is fast and feasible, yet can miss a better combination. Branch and bound combines a systematic search with a proof that some unfinished choices cannot improve the answer already found.

The same idea applies to discrete optimization problems such as facility location, scheduling, routing, and integer programming. Backtracking asks whether a partial choice can still be feasible. Branch and bound adds a second question: even if this branch remains feasible, could its best possible completion beat the incumbent? If an optimistic bound says no, the whole branch can be discarded.

This lesson uses 0/1 knapsack maximization as a concrete implementation. You will distinguish feasible solutions from optimistic estimates, derive a fractional relaxation bound, trace both kinds of pruning, and implement a depth-first search with explicit state and exact arithmetic. The search returns one optimal subset and explains why its exponential worst case remains possible.

Core Concepts and Terminology

For knapsack, item $j$ has positive integer weight $w_j$ and nonnegative integer value $v_j$. Choose $x_j\in\{0,1\}$ to solve

$$\max\sum_{j=0}^{n-1}v_jx_j\qquad\text{subject to}\qquad\sum_{j=0}^{n-1}w_jx_j\le W.$$

Every item is optional, so the empty subset is feasible and has value zero. The programs return the maximum value, the chosen subset's weight, and its original item IDs. They return one optimum; they do not promise the lightest, lexicographically smallest, or every tied optimal subset.

The incumbent is a known feasible subset with value $B$. For maximization, it provides a lower bound on the global optimum. For a search node $s$, let $\operatorname{OPT}(s)$ be the best integer value among its completions. A valid optimistic upper bound must satisfy

$$U(s)\ge\operatorname{OPT}(s).$$

Therefore prune when $U(s)\le B$: no completion can improve the saved solution. A feasible greedy packing is suitable for initializing $B$, but its value is generally not an upper bound. A fractional solution may be suitable for computing $U$, but generally cannot become the incumbent.

Sort the items by decreasing value-to-weight ratio, breaking equal ratios by original ID. A node at depth $i$ has fixed include/exclude decisions for the first $i$ sorted items. Its selected-ID stack, current weight $w$, current value $p$, and next index $i$ describe the residual problem. Items before $i$ that are absent from the stack were excluded. The stack alone is insufficient: selecting [0] after excluding item 1 describes a different residual problem from selecting [0] before deciding item 1.

The picture summarizes the worked example's search tree. Its left subtree is collapsed; the later full trace lists all seventeen visits. The two bound-pruned branches on the right are evaluated after the incumbent has reached 98, even though their parent was entered when it was 88.

How Branch and Bound Works, Step by Step

The bound comes from fractional knapsack. Keep the node's past decisions fixed, but permit fractions of remaining items. This enlarges the feasible set, so its maximum value cannot be smaller than the best integer completion. In decreasing density order, take whole remaining items while they fit, then take the fraction of the first item that fills the remaining capacity and stop.

Why does that order solve the relaxation? If a fractional packing uses some lower-density weight while a higher-density item still has available weight, exchange the same weight between them. Value cannot decrease. Repeating this exchange yields a packing with a whole prefix, at most one fractional item, and no later items.

If whole items add value $q$, and $r$ units of capacity remain for the next item of weight $w_k$ and value $v_k$, the fractional bound is

$$U_{\mathrm{frac}}=p+q+\frac{rv_k}{w_k}.$$

All feasible objective values are integers, so the tighter integer bound

$$U=p+q+\left\lfloor\frac{rv_k}{w_k}\right\rfloor$$

is still safe. If an integer $z\le U_{\mathrm{frac}}$, then $z\le\lfloor U_{\mathrm{frac}}\rfloor$. This floor operation is justified by the integer objective; it is not a general rounding rule for real-valued optimization. If all remaining items fit, simply add all their values.

The implementation follows this order:

1. Copy and sort the items by exact density comparisons. To compare items $a$ and $b$, compare $v_aw_b$ and $v_bw_a$ instead of dividing into floating-point ratios.
2. Optionally obtain a feasible greedy incumbent: scan the sorted list, taking a positive-value item whenever it fits and skipping items that do not. This whole-item heuristic differs from the bound calculation, which takes a fraction at the first nonfitting item and stops.
3. On each recursive entry, increment nodes. If current weight exceeds capacity, increment infeasible and return. Positive weights make this failure irreversible within that include branch.
4. For a feasible state, update the incumbent if the selected items' value is strictly better. Leaving every undecided item out completes that partial selection feasibly, so an update need not wait for depth $n$.
5. If all items have been decided, count a feasible terminal leaf and return. Otherwise compute the upper bound. If $U\le B$, count a bound prune and return.
6. Include the next item: push its original ID and add its weight and value. Recurse to $i+1$. On return, subtract that value and weight and pop its ID.
7. Explore exclusion at $i+1$ using the restored parent state. The global incumbent retains every improvement found in the include subtree. After all branches return, output its saved witness.

Only branch-specific state is undone. The incumbent is a global record of a feasible solution, so restoring it to an older value would throw away progress and weaken later pruning. The saved incumbent IDs are copied from the current selection; they must not alias the mutable stack.

The code deliberately counts an overweight include call as a visit before rejecting it. An implementation that checks the weight before making that call can explore the same feasible states with a different node counter. Likewise, this implementation checks terminal leaves before computing their bound, which determines the trace's bounds and leaves totals.

flowchart TD
    A["Copy and sort items; initialize feasible incumbent"] --> B["Enter search at next index i; increment nodes"]
    B --> C{"Weight exceeds capacity?"}
    C -->|Yes| D["Count infeasible visit; return"]
    C -->|No| E["Save selection if its value improves incumbent"]
    E --> F{"All items decided?"}
    F -->|Yes| G["Count feasible leaf; return"]
    F -->|No| H["Compute fractional integer upper bound U"]
    H --> I{"U no greater than incumbent?"}
    I -->|Yes| J["Count bound prune; return"]
    I -->|No| K["Push next item; add its weight and value"]
    K --> L["Recurse on include branch at i+1"]
    L --> M["Subtract value and weight; pop item"]
    M --> N["Recurse on exclude branch at i+1"]
    N --> O["Return with parent state restored"]

Worked Example with a Full Trace

Capacity is $W=10$. Item IDs already appear in the density order used by the programs:

Greedy seeding takes item 0, skips items 1 and 2 because they do not fit, takes item 3, and skips item 4. Its witness [0,3] weighs 8 and has value 75. Initialize $B=75$. For the root bound, take item 0 and $4/5$ of item 1:

$$U_{\mathrm{frac}}=60+\frac45\cdot49=99.2,\qquad U=99.$$

Since $99\gt75$, search must continue. Including item 0 also has upper bound 99. Trying to include item 1 or, after excluding it, item 2 produces weight 11, so those include calls fail immediately. With both items 1 and 2 excluded, the bound becomes $60+15+\lfloor(2\cdot28)/4\rfloor=89$.

Including item 3 next yields weight 8 and value 75. The fractional bound is still 89, so the solver explores item 4. Including it produces weight 12 and fails; excluding it reaches a leaf of value 75. Undo item 3. Now item 4 fits with item 0, and their value 88 improves the incumbent. The next leaf, item 0 alone, cannot improve it.

After undoing the entire item-0 include branch, exclude item 0. The bound is 98: take items 1 and 2 in full. Include item 1, then item 2. At this feasible partial selection the solver immediately saves value 98, then prunes its remaining choices because its upper bound is exactly 98. The two pending branches have upper bound 85 and are also pruned.

Here is every recursive entry, in the same order as the code. i is the next sorted item index; missing items before i have been excluded. A dash means the code returns before calculating a bound. The incumbent column is recorded after the entry's possible update.

The three overweight calls are nodes 3, 5, and 8. The feasible terminal leaves are nodes 9, 11, and 12. Bounds are computed at eleven nonterminal feasible entries. The incumbent improves at node 11, from 75 to 88, and node 15, from 88 to 98. Bound prunes occur at nodes 15, 16, and 17.

For node 16, item 2 has been excluded after choosing item 1. Take item 3 fully and three quarters of item 4 in the relaxation:

$$U=49+15+\left\lfloor\frac{3\cdot28}{4}\right\rfloor=85\le98.$$

For node 17, both items 0 and 1 were excluded. Take item 2, item 3, and the same fraction of item 4, again obtaining 85. Both branches are settled without visiting their leaves. The final answer is value 98, weight 10, original IDs [1,2]. The active selection is empty and its weight and value are zero after all undo operations.

Implementation in Python, C++, and Java

Each panel is a complete runnable implementation of the same depth-first algorithm. Input weights and values are aligned by original zero-based item ID; sorting keeps that ID attached to each item. The constructor copies the inputs, sorts by decreasing exact density, and breaks density ties by ID. The returned IDs are sorted numerically for display, independently of search order.

The demonstration accepts up to 24 items. Capacity and each value are integers in $[0,10^9]$; weights are integers in $[1,10^9]$. Arrays must be non-null and have equal lengths. Python additionally rejects noninteger values rather than coercing them. Zero-value items are permitted; zero-weight and negative inputs are rejected. These assumptions keep capacity pruning monotone and the fractional bound well-defined.

C++ and Java use 64-bit arithmetic for weights, values, density cross-products, fractional numerators, and counters. A single product is at most $10^{18}$, and total selected weight or value is at most $24\cdot10^9$, within their signed 64-bit range. Do not raise the input limits without revisiting those products and totals. Python uses exact integers but observes the same accepted input range. No floating-point calculations appear in the solver.

solve resets the working selection and all counters, optionally seeds a feasible greedy solution, and runs the search to completion. The method can be called repeatedly with either seeding mode on the same object. It verifies the final selection, weight, and value were restored. The saved answer is copied, so later undo operations or another solve do not change a previous result.

Counters have the following meanings:

• nodes: all recursive entries, including overweight calls, bound prunes, and feasible leaves.
• bounds: upper-bound calculations at feasible nonterminal entries.
• infeasible: calls rejected because their current weight exceeds capacity.
• pruned: feasible nonterminal entries rejected by $U\le B$.
• updates: strict incumbent improvements found during search, excluding initial greedy seeding.
• leaves: feasible entries at depth $n$, whether or not they improve the answer.

The terminal categories partition all returns: an entry either branches, is infeasible, is bound-pruned, or is a feasible leaf. bounds is a work counter that overlaps branching and bound-pruned entries. The seed field is the initial feasible value, not an extra counter or an optimality claim.

from functools import cmp_to_key


class KnapsackBB:
    LIMIT = 1_000_000_000

    def __init__(self, capacity, weights, values):
        if type(capacity) is not int or not 0 <= capacity <= self.LIMIT:
            raise ValueError("capacity out of range")
        if len(weights) != len(values) or len(weights) > 24:
            raise ValueError("invalid item counts")
        for w, v in zip(weights, values):
            if (type(w) is not int or type(v) is not int or
                    not 1 <= w <= self.LIMIT or not 0 <= v <= self.LIMIT):
                raise ValueError("invalid weight or value")
        self.capacity = capacity
        self.items = [(i, w, v) for i, (w, v) in enumerate(zip(weights, values))]

        def compare(a, b):
            left, right = a[2] * b[1], b[2] * a[1]
            if left != right:
                return -1 if left > right else 1
            return (a[0] > b[0]) - (a[0] < b[0])

        self.items.sort(key=cmp_to_key(compare))

    def upper(self, index):
        remaining = self.capacity - self.weight
        bound = self.value
        for k in range(index, len(self.items)):
            _, w, v = self.items[k]
            if w <= remaining:
                remaining -= w
                bound += v
            else:
                bound += remaining * v // w
                break
        return bound

    def search(self, index):
        self.nodes += 1
        if self.weight > self.capacity:
            self.infeasible += 1
            return
        if self.value > self.best:
            self.best, self.best_weight = self.value, self.weight
            self.best_items = self.chosen.copy()
            self.updates += 1
        if index == len(self.items):
            self.leaves += 1
            return
        bound = self.upper(index)
        self.bounds += 1
        if bound <= self.best:
            self.pruned += 1
            return
        rid, w, v = self.items[index]
        self.chosen.append(rid)
        self.weight += w
        self.value += v
        self.search(index + 1)
        self.value -= v
        self.weight -= w
        self.chosen.pop()
        self.search(index + 1)

    def solve(self, seed=True):
        if type(seed) is not bool:
            raise ValueError("seed must be Boolean")
        self.weight = self.value = self.best = self.best_weight = 0
        self.chosen, self.best_items = [], []
        self.nodes = self.bounds = self.infeasible = self.pruned = 0
        self.updates = self.leaves = 0
        if seed:
            for rid, w, v in self.items:
                if v > 0 and self.best_weight + w <= self.capacity:
                    self.best_weight += w
                    self.best += v
                    self.best_items.append(rid)
        self.seed_value = self.best
        self.search(0)
        if self.weight != 0 or self.value != 0 or self.chosen:
            raise RuntimeError("undo failed")
        stats = [self.nodes, self.bounds, self.infeasible, self.pruned,
                 self.updates, self.leaves]
        return self.best, self.best_weight, sorted(self.best_items), self.seed_value, stats


def show(name, capacity, weights, values, seed=True):
    value, weight, items, initial, stats = KnapsackBB(capacity, weights, values).solve(seed)
    print(f"{name}: value={value}, weight={weight}, items=[" + ",".join(map(str, items)) + "]")
    labels = ("nodes", "bounds", "infeasible", "pruned", "updates", "leaves")
    print(f"seed={initial}, " + ", ".join(f"{k}={v}" for k, v in zip(labels, stats)) + ", restored=YES")


def main():
    w, v = [6, 5, 5, 2, 4], [60, 49, 49, 15, 28]
    show("worked", 10, w, v)
    show("unseeded", 10, w, v, False)
    show("root proof", 10, [2, 3, 5, 4], [40, 50, 65, 50])
    show("ties", 4, [2, 2, 4], [3, 3, 6])
    show("large", 1_000_000_000, [999_999_999, 500_000_000, 500_000_000],
         [1_000_000_000, 500_000_001, 500_000_001])
    show("close ratios", 1_000_000_000, [999_999_999, 999_999_998], [1_000_000_000, 999_999_999])
    show("wide total", 3, [1, 1, 1], [1_000_000_000] * 3)
    show("zero capacity", 0, [1, 2], [5, 9])
    show("empty", 10, [], [])
    print("checks = PASS")


if __name__ == "__main__":
    main()

#include <algorithm>
#include <iostream>
#include <stdexcept>
#include <string>
#include <vector>
using namespace std;

struct Item { int id; long long weight, value; };
struct Result {
    long long value, weight, seed;
    vector<int> items;
    vector<long long> stats;
};

class KnapsackBB {
public:
    static constexpr long long LIMIT = 1000000000LL;
    long long capacity, weight=0, value=0, best=0, best_weight=0, seed_value=0;
    vector<Item> items;
    vector<int> chosen, best_items;
    long long nodes=0, bounds=0, infeasible=0, pruned=0, updates=0, leaves=0;

    KnapsackBB(long long cap, const vector<long long>& weights, const vector<long long>& values)
        : capacity(cap) {
        if (cap<0 || cap>LIMIT || weights.size()!=values.size() || weights.size()>24)
            throw invalid_argument("invalid capacity or item counts");
        for (size_t i=0;i<weights.size();++i) {
            if (weights[i]<1 || weights[i]>LIMIT || values[i]<0 || values[i]>LIMIT)
                throw invalid_argument("invalid weight or value");
            items.push_back({static_cast<int>(i),weights[i],values[i]});
        }
        sort(items.begin(),items.end(),[](const Item& a,const Item& b) {
            long long left=a.value*b.weight, right=b.value*a.weight;
            if (left!=right) return left>right;
            return a.id<b.id;
        });
    }

    long long upper(int index) const {
        long long remaining=capacity-weight, bound=value;
        for (int k=index;k<static_cast<int>(items.size());++k) {
            const Item& item=items[k];
            if (item.weight<=remaining) {
                remaining-=item.weight; bound+=item.value;
            } else {
                bound+=remaining*item.value/item.weight;
                break;
            }
        }
        return bound;
    }

    void search(int index) {
        ++nodes;
        if (weight>capacity) { ++infeasible; return; }
        if (value>best) {
            best=value; best_weight=weight; best_items=chosen; ++updates;
        }
        if (index==static_cast<int>(items.size())) { ++leaves; return; }
        long long bound=upper(index); ++bounds;
        if (bound<=best) { ++pruned; return; }
        const Item& item=items[index];
        chosen.push_back(item.id); weight+=item.weight; value+=item.value;
        search(index+1);
        value-=item.value; weight-=item.weight; chosen.pop_back();
        search(index+1);
    }

    Result solve(bool seed=true) {
        weight=value=best=best_weight=0;
        chosen.clear(); best_items.clear();
        nodes=bounds=infeasible=pruned=updates=leaves=0;
        if (seed) {
            for (const Item& item : items)
                if (item.value>0 && best_weight+item.weight<=capacity) {
                    best_weight+=item.weight; best+=item.value; best_items.push_back(item.id);
                }
        }
        seed_value=best;
        search(0);
        if (weight!=0 || value!=0 || !chosen.empty()) throw logic_error("undo failed");
        vector<int> result_items=best_items;
        sort(result_items.begin(),result_items.end());
        return {best,best_weight,seed_value,result_items,
                {nodes,bounds,infeasible,pruned,updates,leaves} };
    }
};

void show(const string& name,long long capacity,const vector<long long>& w,
          const vector<long long>& v,bool seed=true) {
    Result r=KnapsackBB(capacity,w,v).solve(seed);
    cout<<name<<": value="<<r.value<<", weight="<<r.weight<<", items=[";
    for (size_t i=0;i<r.items.size();++i) { if(i) cout<<','; cout<<r.items[i]; }
    cout<<"]\nseed="<<r.seed;
    vector<string> labels={"nodes","bounds","infeasible","pruned","updates","leaves"};
    for (size_t i=0;i<labels.size();++i) cout<<", "<<labels[i]<<'='<<r.stats[i];
    cout<<", restored=YES\n";
}

int main() {
    vector<long long> w={6,5,5,2,4},v={60,49,49,15,28};
    show("worked",10,w,v);
    show("unseeded",10,w,v,false);
    show("root proof",10,{2,3,5,4},{40,50,65,50});
    show("ties",4,{2,2,4},{3,3,6});
    show("large",1000000000LL,{999999999,500000000,500000000},
         {1000000000,500000001,500000001});
    show("close ratios",1000000000LL,{999999999,999999998},{1000000000,999999999});
    show("wide total",3,{1,1,1},{1000000000,1000000000,1000000000});
    show("zero capacity",0,{1,2},{5,9});
    show("empty",10,{},{});
    cout<<"checks = PASS\n";
}

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main {
    static final class Item {
        int id;
        long weight,value;
        Item(int id,long weight,long value) { this.id=id; this.weight=weight; this.value=value; }
    }
    static final class Result {
        long value,weight,seed;
        List<Integer> items;
        long[] stats;
        Result(long value,long weight,long seed,List<Integer> items,long[] stats) {
            this.value=value; this.weight=weight; this.seed=seed;
            this.items=new ArrayList<>(items); this.stats=stats.clone();
        }
    }
    static final class KnapsackBB {
        static final long LIMIT=1_000_000_000L;
        long capacity,weight,value,best,bestWeight,seedValue;
        List<Item> items=new ArrayList<>();
        List<Integer> chosen=new ArrayList<>(),bestItems=new ArrayList<>();
        long nodes,bounds,infeasible,pruned,updates,leaves;

        KnapsackBB(long capacity,long[] weights,long[] values) {
            if(capacity<0 || capacity>LIMIT || weights.length!=values.length || weights.length>24)
                throw new IllegalArgumentException("invalid capacity or item counts");
            this.capacity=capacity;
            for(int i=0;i<weights.length;++i) {
                if(weights[i]<1 || weights[i]>LIMIT || values[i]<0 || values[i]>LIMIT)
                    throw new IllegalArgumentException("invalid weight or value");
                items.add(new Item(i,weights[i],values[i]));
            }
            items.sort((a,b)-> {
                long left=a.value*b.weight,right=b.value*a.weight;
                if(left!=right) return left>right ? -1 : 1;
                return Integer.compare(a.id,b.id);
            });
        }
        long upper(int index) {
            long remaining=capacity-weight,bound=value;
            for(int k=index;k<items.size();++k) {
                Item item=items.get(k);
                if(item.weight<=remaining) { remaining-=item.weight; bound+=item.value; }
                else { bound+=remaining*item.value/item.weight; break; }
            }
            return bound;
        }
        void search(int index) {
            ++nodes;
            if(weight>capacity) { ++infeasible; return; }
            if(value>best) { best=value; bestWeight=weight; bestItems=new ArrayList<>(chosen); ++updates; }
            if(index==items.size()) { ++leaves; return; }
            long bound=upper(index); ++bounds;
            if(bound<=best) { ++pruned; return; }
            Item item=items.get(index);
            chosen.add(item.id); weight+=item.weight; value+=item.value;
            search(index+1);
            value-=item.value; weight-=item.weight; chosen.remove(chosen.size()-1);
            search(index+1);
        }
        Result solve(boolean seed) {
            weight=value=best=bestWeight=0; chosen.clear(); bestItems=new ArrayList<>();
            nodes=bounds=infeasible=pruned=updates=leaves=0;
            if(seed) {
                for(Item item:items)
                    if(item.value>0 && bestWeight+item.weight<=capacity) {
                        bestWeight+=item.weight; best+=item.value; bestItems.add(item.id);
                    }
            }
            seedValue=best;
            search(0);
            if(weight!=0 || value!=0 || !chosen.isEmpty()) throw new IllegalStateException("undo failed");
            List<Integer> resultItems=new ArrayList<>(bestItems); resultItems.sort(Integer::compare);
            return new Result(best,bestWeight,seedValue,resultItems,
                              new long[] {nodes,bounds,infeasible,pruned,updates,leaves});
        }
    }
    static void show(String name,long capacity,long[] w,long[] v,boolean seed) {
        Result r=new KnapsackBB(capacity,w,v).solve(seed);
        StringBuilder out=new StringBuilder(name+": value="+r.value+", weight="+r.weight+", items=[");
        for(int i=0;i<r.items.size();++i) { if(i>0) out.append(','); out.append(r.items.get(i)); }
        System.out.println(out+"]"); out=new StringBuilder("seed="+r.seed);
        String[] labels={"nodes","bounds","infeasible","pruned","updates","leaves"};
        for(int i=0;i<labels.length;++i) out.append(", ").append(labels[i]).append('=').append(r.stats[i]);
        System.out.println(out+", restored=YES");
    }
    public static void main(String[] args) {
        long[] w={6,5,5,2,4},v={60,49,49,15,28};
        show("worked",10,w,v,true);
        show("unseeded",10,w,v,false);
        show("root proof",10,new long[] {2,3,5,4},new long[] {40,50,65,50},true);
        show("ties",4,new long[] {2,2,4},new long[] {3,3,6},true);
        show("large",1_000_000_000L,new long[] {999_999_999,500_000_000,500_000_000},
             new long[] {1_000_000_000,500_000_001,500_000_001},true);
        show("close ratios",1_000_000_000L,new long[] {999_999_999,999_999_998},
             new long[] {1_000_000_000,999_999_999},true);
        show("wide total",3,new long[] {1,1,1},new long[] {1_000_000_000,1_000_000_000,1_000_000_000},true);
        show("zero capacity",0,new long[] {1,2},new long[] {5,9},true);
        show("empty",10,new long[] {},new long[] {},true);
        System.out.println("checks = PASS");
    }
}

Expected stdout, identical in all three languages:

• worked: value=98, weight=10, items=[1,2]
• seed=75, nodes=17, bounds=11, infeasible=3, pruned=3, updates=2, leaves=3, restored=YES
• unseeded: value=98, weight=10, items=[1,2]
• seed=0, nodes=17, bounds=11, infeasible=3, pruned=3, updates=4, leaves=3, restored=YES
• root proof: value=155, weight=10, items=[0,1,2]
• seed=155, nodes=1, bounds=1, infeasible=0, pruned=1, updates=0, leaves=0, restored=YES
• ties: value=6, weight=4, items=[0,1]
• seed=6, nodes=1, bounds=1, infeasible=0, pruned=1, updates=0, leaves=0, restored=YES
• large: value=1000000002, weight=1000000000, items=[1,2]
• seed=1000000002, nodes=1, bounds=1, infeasible=0, pruned=1, updates=0, leaves=0, restored=YES
• close ratios: value=1000000000, weight=999999999, items=[0]
• seed=999999999, nodes=7, bounds=3, infeasible=1, pruned=0, updates=1, leaves=3, restored=YES
• wide total: value=3000000000, weight=3, items=[0,1,2]
• seed=3000000000, nodes=1, bounds=1, infeasible=0, pruned=1, updates=0, leaves=0, restored=YES
• zero capacity: value=0, weight=0, items=[]
• seed=0, nodes=1, bounds=1, infeasible=0, pruned=1, updates=0, leaves=0, restored=YES
• empty: value=0, weight=0, items=[]
• seed=0, nodes=1, bounds=0, infeasible=0, pruned=0, updates=0, leaves=1, restored=YES
• checks = PASS

The root proof case already has a feasible value equal to its fractional integer bound, so one root visit proves optimality. ties returns items [0,1], although item [2] has the same value and weight. The algorithm preserves its first incumbent when an equal-value alternative exists. wide total checks that the value can exceed a signed 32-bit integer. The two densities in close ratios differ by less than $2\cdot10^{-18}$, so their exact ordering must not be replaced by rounded ratios.

Validation compared 6,413 inputs per language with seeding disabled and enabled, for 12,826 mode/input cases per language, including nine invalid inputs. The valid corpus includes all ordered item lists of lengths zero through three with weights in $\{1,2\}$ and values in $\{0,1,2,3\}$ under capacities zero through six; 2,000 seeded random instances; 300 instances with large integers; and boundary fixtures up to 24 items. Independent subset enumeration, with capacity-state dynamic programming for the larger boundary fixtures, checked optimal values. An immutable search model checked the exact witness and all six counters. Repeated solves preserved inputs and returned identical results.

The bound audit used a separate exact formulation. For remaining capacity $R$, the fractional optimum can also be obtained from the one-variable LP dual

$$\min_{\lambda\ge0}\left(\lambda R+\sum_j\max(0,v_j-\lambda w_j)\right).$$

The audit tested zero and every remaining density as candidate breakpoints using rational arithmetic. It checked 125,220 bound computations against this independent relaxation calculation and against exact residual integer optima. It also checked 49,766 safe prunes and 176,524 state-restoration and feasible-incumbent checks. Across the valid corpus, greedy seeding reduced visits in 3,700 inputs and left them unchanged in 2,704. C++ ran with address and undefined-behavior sanitizers; Java ran with assertions enabled. These figures describe the validation corpus, rather than a performance guarantee for arbitrary inputs.

Complexity, Correctness, and Invariants

Let $n$ be the item count and $N$ the number of recursive entries, including infeasible calls. Analyze growing inputs rather than treating the demonstration's fixed limits as a constant-size problem. Density sorting costs $O(n\log(n+1))$ comparisons, and greedy initialization costs $O(n)$. Under the accepted integer limits, the arithmetic in each comparison fits in a machine integer.

At a feasible nonterminal entry, the bound scans at most $n-i$ remaining items. Copying a new incumbent's IDs costs at most $O(n)$, and ordinary include/undo operations are constant time. A conservative total bound is

$$T=O\bigl(n\log(n+1)+N(n+1)\bigr),\qquad N\le2^{n+1}-1.$$

Thus a conservative worst-case bound is $O((n+1)2^n+n\log(n+1))$. Branch and bound can still explore an exponentially large tree when the relaxation is weak or many branches remain competitive. There is no distribution-independent average-case improvement: item correlations, capacity, tie structure, and incumbent quality affect pruning.

In a best case such as root proof, $N=1$: sorting and one linear bound calculation settle the problem, giving $O(n\log(n+1))$ total time here. With an already sorted input, the corresponding search and initialization take $O(n)$. For an empty input, one terminal call takes constant time. A zero capacity also settles at the root for nonempty accepted inputs, since all weights are positive.

The search holds one mutable selection and at most $n+1$ recursive frames. The copied items, incumbent IDs, returned witness, and sorting workspace use $O(n)$ memory overall. It does not store all live siblings in a separate frontier. This distinguishes depth-first search from a best-bound implementation, which may retain exponentially many open nodes.

Correctness separates partitioning, feasibility, bounding, and undo. At depth $i$, including and excluding the next item partition every completion of the fixed prefix. Positive weights make an overweight selection permanently infeasible in that branch. For a feasible selection, taking no further items gives an immediate feasible witness, so every incumbent update is valid.

Relaxing the remaining binary decisions to fractions contains every integer completion. Density filling solves that relaxation; flooring its value preserves an upper bound on integer objectives. Hence $U\le B$ can remove only branches incapable of strict improvement. An equal-valued optimum may be discarded because the incumbent already supplies a witness of that value. Restoring the selection, weight, and value after inclusion makes the exclusion branch describe exactly the intended sibling problem. After the finite search has settled every branch, no better feasible selection remains, so the incumbent is optimal.

Variants, Pitfalls, and Optimizations

Maximization versus minimization. For maximization, feasible incumbents are lower bounds on the optimum, and optimistic node estimates are upper bounds; prune when $U\le B$. For minimization, a feasible incumbent is an upper bound, and an optimistic node estimate is a lower bound; prune when $L\ge B$. The word “optimistic” means better than or equal to every attainable completion, with the inequality direction determined by the objective.

Feasible heuristics versus relaxations. The worked greedy packing of value 75 proves only that the optimum is at least 75. Calling that number an upper bound would falsely prune the root and lose the solution worth 98. Conversely, the fractional packing worth 99.2 is not a permissible 0/1 witness. Keep the bound and incumbent roles explicit even if a solver reports both as numbers.

Search strategy and warm starts. Depth first uses little memory and may find a complete feasible solution quickly. Best-bound search prioritizes the largest upper bound for maximization, while breadth first explores decision levels uniformly. All can be correct with sound pruning; they differ in incumbent discovery and frontier size. A better feasible warm start can strengthen pruning. The code applies the whole-item heuristic only at the root; running a completion heuristic at selected internal nodes may improve the incumbent earlier, at an additional cost.

Stronger bounds. The sum of all remaining values is a valid but often loose upper bound for this nonnegative-value problem. Fractional knapsack is tighter because it respects capacity. More general integer programs use LP relaxations, valid inequalities, and other problem-specific bounds; adding valid cutting planes gives branch and cut. A stronger bound is useful only when the saved search justifies its computation cost. Prefix sums and a search for the fractional break item can accelerate this fixed-order knapsack bound, while an exact residual DP can sometimes settle small subproblems directly.

Arithmetic and input assumptions. Density order is part of the bound's proof. A rounded ratio or an overflowing cross-product can put items in the wrong order and invalidate the claimed fractional optimum. The code therefore uses exact comparisons and validates limits before multiplication. Flooring is safe here because the objective is integer and the fractional value is computed exactly; a floating-point underestimate near an integer can still be unsafe. Real-valued objectives require an appropriate conservative bound rather than this integer truncation rule.

Zero-weight items with positive value would be worth preprocessing if zero weights were supported: take them once in 0/1 knapsack and adjust the objective. The shown implementation rejects zero weights instead. Negative weights would also invalidate the argument that an overweight prefix can never become feasible. The accepted input model is part of the algorithm's correctness conditions.

Ties and dominance. Pruning equality is correct when only one optimal witness is required. Enumerating every optimum needs strict bound pruning, appropriate tie collection, and a terminal policy that avoids reporting the same completed selection from several partial states. It is not obtained by changing one comparison alone. Be equally careful with item dominance: an item that is heavier and no more valuable than another cannot always be deleted in 0/1 knapsack, because an optimum may use both distinct items. State dominance requires the same remaining decisions and a proof that one partial state can replace the other.

Stopping early and reporting a gap. An incumbent alone gives a feasible answer. To report an optimality gap before exhaustion, maintain valid bounds for the entire open frontier, including pending siblings and the currently explored subproblem. For maximization,

$$B\le\operatorname{OPT}\le U_{\mathrm{global}},\qquad U_{\mathrm{global}}=\max\left(B,\max_{s\in\mathrm{OPEN}}U(s)\right).$$

The absolute gap is $U_{\mathrm{global}}-B$. With an empty frontier, define the global bound as $B$. The last visited node's bound is not necessarily a bound for the whole problem. The supplied recursive solver runs to completion and does not implement interruption or frontier-gap reporting. In other optimization problems, distinguish “no incumbent yet” from proven infeasibility; this optional-item knapsack always has the empty feasible solution.

Practice Problems and Real-World Use

Begin by checking small instances against every item subset. Validate both the claimed optimum and its witness: IDs must be distinct, weights must fit, and values must sum to the reported objective. Instrument bounds separately from node counts. A fast program with an invalid upper bound can produce a plausible but wrong answer; measuring fewer visits does not establish correctness.

The branch-and-bound framework extends beyond knapsack, but its bound must be re-derived for each problem. For facility location, a minimization relaxation can underestimate opening and shipping costs. For routing, a relaxation can underestimate the cost of completing a tour. For scheduling, a lower bound on achievable makespan can settle branches whose jobs still look feasible. A correct bound may ignore some constraints to become optimistic; it must not exclude legal completions while claiming to represent all of them.

For further reading, MIT's branch-and-bound lecture develops node selection and a facility-location example. Carnegie Mellon's knapsack example connects the integer formulation with its fractional relaxation. The programs and measured trace here are a separate small implementation with the stated input contract.