3
依次从表PT中选取使目标函数的值取得极值的结点成 为当前扩展结点，重复上述过程，直到找到最优解。
随着这个遍历过程的不断深入，表PT中所估算的目标函 数的界越来越接近问题的最优解。当搜索到一个叶子结点时 ，如果该结点的目标函数值是表PT中的极值（对于最小化问 题，是极小值；对于最大化问题，是极大值），则该叶子结 点对应的解就是问题的最优解。
限界函数为：
u b v ( W w ) ( v i 1w i 1 )
2021/2/27
6
分支限界法求解0/1背包问题
1 w=0, v=0 ub=100
2 w=4, v=40 ub=76
4×
w=11 无效解
5 w=4, v=40 ub=70
6 w=9, v=65 ub=69
7 w=4, v=40 ub=64
物品 1
重量(w) 价值(v)
4
40
价值/重量 (v/w)
10
2
7
42
6
3
5
25
5
4
3
12
4
2021/2/27
5
应用贪心法求得近似解为(1, 0, 0, 0)，获得的价 值为40，这可以作为0/1背包问题的下界。
如何求得0/1背包问题的一个合理的上界呢？
考虑最好情况，背包中装入的全部是第1个物品 且可以将背包装满，则可以得到一个非常简单的上界 的计算方法：ub=W×(v1/w1)=10×10=100。于是，得 到了目标函数的界[40, 100]。
2021/2/27
11
若某孩子结点的目标函数值超出目标函数的界，则将 该孩子结点丢弃；否则，将该孩子结点保存在待处理结点 表PT中。
从表PT中选取使目标函数取得极大值的结点作为下一 次扩展的根结点，重复上述过程，当到达一个叶子结点时， 就 得 到 了 一 个 可 行 解 X=(x1, x2, …, xn) 及 其 目 标 函 数 值 bound(x1, x2, …, xn)。
