0-1背包问题 上界函数 ∥n表示物品总数，cleft为剩余空间 while (i<=n &wli]<cleft) cleft -wlil; w表示所占空间 b+=p; p]表示的价值 计+； } if(i<=n)b+=p[/w问*cleft;∥装填剩余容量装满背包 return b; b为上界函数
0-1背包问题 上界函数 // n表示物品总数，cleft为剩余空间 while (i <= n && w[i] <= cleft) { cleft -= w[i]; //w[i]表示i所占空间 b += p[i]; //p[i]表示i的价值 i++; } if (i <= n) b+=p[i]/w[i] * cleft; // 装填剩余容量装满背包 return b; //b为上界函数
0-1背包问题 while(i!=n+1){∥非叶结点 ∥检查当前扩展结点的左儿子结点 分支限界搜索过 程 Typew wt=cw wlil; if(wt<=c){∥左儿子结点为可行结点 if (cp+pli]bestp)bestp cp+pli]; AddLiveNode(up,cp+p[i],cw+w[i],true,i+1);} up Bound(i+1); ∥检查当前扩展结点的右儿子结点 if(up>=bestp)∥右子树可能含最优解 AddLiveNode(up,cp,cw,false,i+1); ∥取下一个扩展结点（略）}
0-1背包问题 while (i != n+1) { // 非叶结点 // 检查当前扩展结点的左儿子结点 Typew wt = cw + w[i]; if (wt <= c) { // 左儿子结点为可行结点 if (cp+p[i] > bestp) bestp = cp+p[i]; AddLiveNode(up, cp+p[i], cw+w[i], true, i+1);} up = Bound(i+1); // 检查当前扩展结点的右儿子结点 if (up >= bestp) // 右子树可能含最优解 AddLiveNode(up, cp, cw, false, i+1); // 取下一个扩展结点（略）} 分支限界搜索过 程
0/1背包的分支限界法过程 总结 从0/1背包问题的搜索过程可看出：与回溯法相 比，分支限界法可根据限界函数不断调整搜索 方向，选择最可能得最优解的子树优先进行搜 索→找到问题的解
0/1背包的分支限界法过程 总结 从0/1背包问题的搜索过程可看出：与回溯法相 比，分支限界法可根据限界函数不断调整搜索 方向，选择最可能得最优解的子树优先进行搜 索→找到问题的解
分支限界法的设计思路 设求解最大化问题，解向量为X(X,X),的取 值范围为SS小=。在使用分支限界搜索问题的解 空间树时，先根据限界函数估算目标函数的界[down, w,然后从根结点出发，扩展根结点的个孩子结 点，从而构成分量x的种可能的取值方式。 对这，个孩子结点分别估算可能的目标函 X1 数bound《x),其含义：以该结点为根的 子树所有可能的取值不大于bound心x), 即： X2 bound《x1)≥bound(x.x2)≥..≥ bound(x1,Xn）
分支限界法的设计思路 设求解最大化问题，解向量为X=(x1 ,…,xn )，xi 的取 值范围为Si，|Si |=ri。在使用分支限界搜索问题的解 空间树时，先根据限界函数估算目标函数的界[down, up]，然后从根结点出发，扩展根结点的r1个孩子结 点，从而构成分量x1的r1种可能的取值方式。 对这r1个孩子结点分别估算可能的目标函 数bound(x1 )，其含义：以该结点为根的 子树所有可能的取值不大于bound(x1 )， 即： bound(x1 )≥bound(x1 ,x2 )≥…≥ bound(x1 ,…,xn ) x1 x2 ... x2 r1
分支限界法的设计思路 ?若某孩子结点的目标函数值小 于目标函数的下界，则将该孩 子结点丢弃；否则，将该孩子 结点保存在待处理结点表PT 是 是否PT中最大值？ 中。 3再取PT表中目标函数极大值 则X是问题 用X来调整down 结点作为扩展的根结点，重复 的最优解； 上述步骤。 bound是最少所能 得到的解 3直到一个叶子结点时的可行解 X仁(，n),及目标函数值 继续搜索 b0und(X,X)
分支限界法的设计思路 若某孩子结点的目标函数值小 于目标函数的下界，则将该孩 子结点丢弃；否则，将该孩子 结点保存在待处理结点表PT 中。 再取PT表中目标函数极大值 结点作为扩展的根结点，重复 上述步骤。 直到一个叶子结点时的可行解 X=(x1 ,…,xn )，及目标函数值 bound (x1 ,…,xn )。 是 是否PT中最大值？ 否 则X是问题 的最优解； 用X来调整down bound是最少所能 得到的解 继续搜索