分支定界法

分支定界法（branch and bound）把一个优化问题拆成覆盖原可行域的子问题，并用可靠的目标界限排除不可能改善当前方案的部分。它兼有搜索和证明两种任务：找到可行方案给出一个已达到的值，证明其余分支无法更好才确认最优。

考虑两个物品，重量都为三，价值分别为五和四，容量为四；每个物品最多选一次。全部可行整数选择只有不选、只选A、只选B，价值分别为零、五、四。最优值显然为五，但这张小搜索树足以说明界限怎样工作。

分数装入给出上界

把选择变量 $a,b\in \{0,1\}$ 放宽到 $[0,1]$，有 $$\begin{array}{cc}max& 5a+4b,\\ 3a+3b& \le 4,\\ 0& \le a,b\le 1.\end{array}$$ 先装价值密度较高的A，再用剩余容量装三分之一个B，得到松弛值 $5+4/3=19/3$。其上界性质可以直接证明：将容量式乘 $4/3$，再加上 $a\le 1$，得到 $5a+4b\le 19/3$；分数方案又达到该界。

若用这类分数背包为一般节点计算上界，按价值除以重量递减装入是正确的：假设较低密度物品占有正重量，而较高密度物品尚有空缺，把同量重量移过去，价值不会降低。反复交换，便得到按密度顺序装满、至多一个物品只装部分的形式。这个交换证明只用于允许分数、重量正且价值非负的松弛。

分支和剪枝的逻辑

对原问题按A是否被选建立 $a=0$ 与 $a=1$ 两支，每个整数方案恰好落入一支，因而不会漏解。若先沿 $a=1,b=0$ 找到价值五的可行解，当前最佳值记为 $L=5$。

另一支 $a=0$ 的上界只有四，满足 $U\le L$，可以剪去。$a=1$ 这一支中，$b=1$ 重量为六，不可行；$b=0$ 则给出已经记录的五。所有分支处理完，才得到最优性证明。

分支覆盖整数选择；标出的U是上界，L是已找到的可行值。剪枝比较的是界限，不能拿未经保证的估计值代替。

更一般地，最大化节点的所有可行解都应满足目标不超过 $U$。若 $U\le L$，其中不可能有严格改善当前解的方案；如果上界来自扩大的松弛域，这一点由集合包含关系保证。最小化时，松弛给下界，已有可行方案给上界，剪枝方向相应反过来。

一个精确有理数实现

代码输入非负整数价值、正整数重量及非负整数容量，返回最大价值与原物品顺序下的选择向量。采用深度优先搜索，每次先试选入；Fraction 使分数上界的比较保持精确。递归到第 $k$ 层时，前 $k$ 个选择已固定，当前重量与价值正好是这些物品的合计；分支维持这一不变量，且剩余物品均由有效松弛上界覆盖。

最坏仍有指数多个节点。忽略整数位运算成本，计算节点界限需 $O(n)$，最坏时间 $O(n{2}^n)$；深度为 $n$，代码递归保留选择元组，额外空间为 $O(n^2)$。它用于可完整核验的小规模问题，较大的实例需专业求解器的预处理、割与搜索策略。

Python 3

from fractions import Fraction

def branch_bound_knapsack(weights, values, capacity):
    w, v = tuple(weights), tuple(values)
    if len(w) != len(v) or type(capacity) is not int or capacity < 0:
        raise ValueError("matching arrays and nonnegative integer capacity required")
    if any(type(x) is not int or x <= 0 for x in w):
        raise ValueError("weights must be positive integers")
    if any(type(x) is not int or x < 0 for x in v):
        raise ValueError("values must be nonnegative integers")
    items = sorted(range(len(w)), key=lambda i: Fraction(v[i], w[i]), reverse=True)
    best_value, best_bits = 0, (0,) * len(w)
    def upper(k, used, value):
        room, bound = capacity - used, Fraction(value)
        for j in items[k:]:
            amount = min(room, w[j])
            bound += Fraction(amount * v[j], w[j])
            room -= amount
            if room == 0:
                break
        return bound
    def visit(k, used, value, selected):
        nonlocal best_value, best_bits
        if value > best_value:
            bits = [0] * len(w)
            for j in selected:
                bits[j] = 1
            best_value, best_bits = value, tuple(bits)
        if k == len(items) or upper(k, used, value) <= best_value:
            return
        j = items[k]
        if used + w[j] <= capacity:
            visit(k + 1, used + w[j], value + v[j], selected + (j,))
        visit(k + 1, used, value, selected)
    visit(0, 0, 0, ())
    return best_value, best_bits

print(branch_bound_knapsack([3, 3], [5, 4], 4))
# (5, (1, 0))

二元变量最多分裂 $n$ 次，故这份有限背包代码一定终止。对一般无界整数模型，任意朴素分支规则却未必保证有限结束；不能从本例的有限树直接推断一般结论。

变式。 容量改为六，两个物品可以同时装入，价值为九；根节点的分数松弛本身已是整数可行方案，界限和已达到值直接相等。容量为零或物品表为空时，最优价值为零。