算法分析与设计-复习提纲.ppt

算法分析与设计,常熟理工学院计算机学院 刘在德,第1章 绪论,掌握三种渐近符号（O、 、 ）的含义； 会用三种渐近符号表示算法的时间复杂度； 会用扩展递归技术分析算法时间的复杂性；对于表示算法时间的简单递推式，能够用扩展递归技术求出最终结果。 P15：例1.6 P18：实验1 P22：习题1.7,三种渐近符号的含义,大O符号：若存在两个正的常数c和n0，对于任意nn0，都有T(n)cf(n)，则称T(n)=O(f(n) 大符号：若存在两个正的常数c和n0，对于任意nn0，都有T(n)cg(n)，则称T(n)=(g(n) 符号：若存在三个正的常数c1、c2和n0，对于任意nn0都有c1f(n)T(n)c2f(n)，则称T(n)=(f(n),渐近符号表示算法时间复杂度,定理1.1 若T(n)=amnm+am-1nm-1+a1n+a0 (am0)，则有T(n)=O(nm)，且T(n)=(nm)，从而T(n)=(nm) 例 T(n)5n28n1 当n1时，5n28n15n28nn5n29n5n29n214n2O(n2) 当n1时，5n28n15n2(n2) 当n1时，14n25n28n15n2 则：5n28n1(n2),用扩展递归技术分析算法时间的复杂性,扩展递归技术：将递推关系式中右边项根据递推式进行逐次替换，得到求和表达式 例,第2章 NP完全理论,对于简单的判定问题，会画判定树。 判定树（Decision Trees）是一棵二叉树：它的每一个内部结点对应一个形如xy的比较，如果关系成立，则控制转移到该结点的左子树，否则，控制转移到该结点的右子树，它的每一个叶子结点表示问题的一个结果。,例 对三个数进行排序的判定树,第3章 蛮力法,掌握改进的串匹配算法KMP算法 理解n个元素的生成排列对象 理解n个元素组成的集合的生成子集 理解0/1背包问题 理解TSP问题,KMP算法,KMP算法思路： 如果某趟在Si和Tj匹配失败后，指针i不回溯；模式T向右滑动至某个位置k，使得tk对准si继续进行匹配。 怎么求k？ 模式T=“t1t2tm”中的每一个字符tj都对应一个k，显然k与S无关。用nextj表示tj对应的k值，则t1tk-1既是t1tj-1的真前缀，又是t1tj-1的真后缀的最长子串，称k是tj的前缀函数值，它等于最长子串长度加1。,next数组的定义,next数组定义如下：,t1=t5,t1t2t3=t3t4t5 a和aba都是ababa的真前缀和真后缀，但aba的长度最大 next6=3+1=4，即当t6和si匹配失败后，将t4和si比较,一个求k的例子：,next数组的求法：,已求出next1, nextj，咋求nextj+1? 设k是tj的前缀函数值，从而有 t1t2tk-1 = tj-k+1tj-k+2tj-1 比较tk和tj，得2种情况： (1) tk=tj：说明t1tk-1tk=tj-k+1tj-1tj，则nextj+1=k+1； (2) tktj：此时要找出t1tj-1的后缀中第2大真前缀nextnextj=nextk, t1tnextk-1=tj-nextk+1tj-1，再比较tnextk和tj，又会出现2种情况：,next数组的求法：,当tnextk=tj时，与(1)类似，nextj+1=nextk+1；当不等时，找第3大真前缀，重复(2)的过程，直至找到t1tj-1后缀中的最大真前缀， 或确定t1tj-1的后缀中没有最大真前缀，此时nextj+1=1。,算法3.4 KMP算法中求next数组,void GetNext (char T , int next ) / 下标从1开始 next1 = 0; j=1; k=0; while (j = m) If (k=0) | (Tj=Tk) j+; k+; nextj=k; else k=nextk ,算法3.5 KMP算法,1. 在串S和T中分别设定比较的起始下标i和j； 2. 循环直到S中所剩字符长度小于T的长度或T中所有字符均比较完毕 2.1 如Si=Tj，则继续比较S和T的下一字符；否则 2.2 将j向右滑动到nextj位置，即j=nextj； 2.3 如果j=0，则将i和j分别加1，准备下一趟比较； 3. 如果T中所有字符均比较完毕，则返回匹配的起始下标，否则返回0。,生成排列对象,思路：假定已生成了1,2,n-1的所有(n-1)!个排列，可以把n插入到n-1个元素的每一种排列的n个位置中去，得到问题规模为n的所有排列。这时排列总数为n(n-1)!=n!。 时间复杂性：O(n!),算法3.9 生成排列对象（伪代码） 1. 生成初始排列1； 2. for (i=2; i=1; k-) 将i插入到第j个排列中的第k个位置；,生成子集,思路：n个元素组成的集合A=a1,a2,an的所有2n个子集与长度为n的所有2n个比特串之间存在一一对应关系。建立这种关系的方法是为每个子集指定一个比特串b1b2bn，如果ai属于该子集，则bi=1，否则bi=0 (1in)。如3个元素组成的集合，比特串110表示a1a2，比特串000表示。,算法3.10 生成子集,1. 初始化一个长度为n的比特串s=000，并将对应的子集输出； 2. for (i=1; i2n; i+) 2.1 s+; 2.2 将s对应的子集输出； 时间复杂性：O(2n)。,0/1背包问题,0/1背包问题：给定n个重量为w1,w2,wn、价值为v1,v2,vn的物品和1个容量为C的背包，求这些物品中的一个最有价值的子集，并能够装到背包中。 思路：考虑给定n个物品集合的所有子集，找出所有可能的子集(总重量不超过背包容量的子集)，计算每个子集的价值，从中找出价值最大子集。,TSP问题,TSP问题：旅行家要旅行n个城市然后回到出发城市，要求各个城市经历且仅经历一次，并要求所经过的路程最短。 思路： 1) 找出所有的Hamilton回路，并计算每个回路的路径长度； 2) 从中选择路径长度最短的回路。,TSP问题,时间复杂性：(n-1)!/2 (出发城市固定，实际旅游了n-1个城市)。 例子： abdca 11 acdba 11,第4/5章 分/ 减治法,理解分治法的基本思路及在典型问题中的应用 掌握递归方法在算法设计中的应用。 掌握减治法在经典问题中的应用 习题4.3 习题4.4 习题5.2,分治法的求解过程,一般来说，分治法的求解过程由以下三个阶段组成： （1）划分：既然是分治，当然需要把规模为n的原问题划分为k个规模较小的子问题，并尽量使这k个子问题的规模大致相同。 （2）求解子问题：各子问题的解法与原问题的解法通常是相同的，可以用递归的方法求解各个子问题，有时递归处理也可以用循环来实现。 （3）合并：把各个子问题的解合并起来，合并的代价因情况不同有很大差异，分治算法的有效性很大程度上依赖于合并的实现。,减治法的设计思想,递 归,递归（Recursion）就是子程序（或函数）直接调用自己或通过一系列调用语句间接调用自己，是一种描述问题和解决问题的基本方法。 递归有两个基本要素： 边界条件：确定递归到何时终止； 递归模式：大问题是如何分解为小问题的。,一个递归和减治法混合应用例子-俄式乘法,习题5的第2题 int rmul(int n, int m) /* 方法1：递归法 */ int halfn, bm, product; if(n=0) return 0; if(n=1) return m;,if(n%2=0) halfn = n1; bm = m1; bm = m1; product = rmul(halfn,bm)+m; return product; ,int rmul(int n, int m) /* 方法2：非递归法 */ int result=0; while(n != 0) if(n%2 = 0) m = m1; return result; ,第6章 动态规划法,掌握动态规划法的设计思想 掌握动态规划法在TSP问题和0/1背包问题中的应用。 给出一个TSP或者0/1背包问题的实例，能够写出它的动态规划过程。 P134：实验6,动态规划法的设计思想,动态规划法将待求解问题分解成若干个相互重叠的子问题，每个子问题对应决策过程的一个阶段，一般来说，子问题的重叠关系表现在对给定问题求解的递推关系（也就是动态规划函数）中，将子问题的解求解一次并填入表中，当需要再次求解此子问题时，可以通过查表获得该子问题的解而不用再次求解，从而避免了大量重复计算。,动态规划法的求解过程,n=5时分治法计算斐波那契数的过程。,例：计算斐波那契数：,动态规划法求解斐波那契数F(9)的填表过程 ：,注意到，计算F(n)是以计算它的两个重叠子问题 F(n-1)和F(n-2)的形式来表达的，所以，可以设计一张表填入n+1个F(n)的值。,TSP问题,TSP问题是指旅行家要旅行n个城市，要求各个城市经历且仅经历一次然后回到出发城市，并要求所走的路程最短。 各个城市间的距离可以用代价矩阵来表示。,假设从顶点i出发，令d(i, V)表示从顶点i出发经过V中各个顶点一次且仅一次，最后回到出发点i的最短路径长度，开始时，VVi，于是，TSP问题的动态规划函数为： d(i,V)=mincik+d(k,Vk)(kV) （式6.5） d(k,)=cki(ki) （式6.6）,这是最后一个阶段的决策，而： d(1, 2, 3)=minc12+d(2, 3), c13+ d(3, 2) d(2, 1, 3)=minc21+d(1, 3), c23+ d(3, 1) d(3, 1, 2)=minc31+d(1, 2), c32+ d(2, 1) 这一阶段的决策又依赖于下面的计算结果： d(1, 2)= c12+d(2, ) d(2, 3)=c23+d(3, ) d(3, 2)= c32+d(2, ) d(1, 3)= c13+d(3, ) d(2, 1)=c21+d(1, ) d(3, 1)=c31+d(1, ),从城市0出发经城市1、2、3然后回到城市0的最短路径长度是： d(0,1, 2, 3)=minc01+d(1, 2, 3), c02+d(2, 1, 3), c03+d(3, 1, 2),而下式可以直接获得（括号中是该决策引起的状态转移）： d(1, )=c10=5(10) d(2, )=c20=6(20) d(3, )=c30=3(30),再向前倒推，有： d(1, 2)= c12+d(2, )=2+6=8(12) d(1, 3)= c13+d(3, )=3+3=6(13) d(2, 3)= c23+d(3, )=2+3=5(23) d(2, 1)= c21+d(1, )=4+5=9(21) d(3, 1)= c31+d(1, )=7+5=12(31) d(3, 2)= c32+d(2, )=5+6=11(32) 再向前倒退，有： d(1, 2, 3)=minc12+d(2, 3), c13+ d(3, 2)=min2+5, 3+11=7(12) d(2, 1, 3)=minc21+d(1, 3), c23+ d(3, 1)=min4+6, 2+12=10(21),d(3, 1, 2)=minc31+d(1, 2), c32+ d(2, 1)=min7+8, 5+9=14(32) 最后有： d(0, 1, 2, 3)=minc01+ d(1, 2, 3), c02+ d(2, 1, 3), c03+ d(3, 1, 2) =min3+7, 6+10, 7+14=10(01) 所以，从顶点0出发的TSP问题的最短路径长度为10，路径是01230。,设顶点之间的代价存放在数组cnn中，动态规划法求解TSP问题的算法如下：,0/1背包问题,在0/1背包问题中，物品i或者被装入背包，或者不被装入背包，设xi表示物品i装入背包的情况，则当xi=0时，表示物品i没有被装入背包，xi=1时，表示物品i被装入背包。根据问题的要求，有如下约束条件和目标函数：,（式6.9）,（式6.10）,于是，问题归结为寻找一个满足约束条件式6.9，并使目标函数式6.10达到最大的解向量X=(x1, x2, , xn)。,0/1背包问题可以看作是决策一个序列(x1, x2, , xn)，对任一变量xi的决策是决定xi=1还是xi=0。在对xi-1决策后，已确定了(x1, , xi-1)，在决策xi时，问题处于下列两种状态之一： （1）背包容量不足以装入物品i，则xi=0，背包不增加价值； （2）背包容量可以装入物品i，则xi=1，背包的价值增加了vi。 这两种情况下背包价值的最大者应该是对xi决策后的背包价值。令V(i, j)表示在前i(1in)个物品中能够装入容量为j（1jC）的背包中的物品的最大值，则可以得到如下动态规划函数： V(i, 0)= V(0, j)=0 （式6.11）,（式6.12）,式6.11表明：把前面i个物品装入容量为0的背包和把0个物品装入容量为j的背包，得到的价值均为0。式6.12的第一个式子表明：如果第i个物品的重量大于背包的容量，则装入前i个物品得到的最大价值和装入前i-1个物品得到的最大价值是相同的，即物品i不能装入背包；第二个式子表明：如果第i个物品的重量小于背包的容量，则会有以下两种情况：（1）如果把第i个物品装入背包，则背包中物品的价值等于把前i-1个物品装入容量为j-wi的背包中的价值加上第i个物品的价值vi；（2）如果第i个物品没有装入背包，则背包中物品的价值就等于把前i-1个物品装入容量为j的背包中所取得的价值。显然，取二者中价值较大者作为把前i个物品装入容量为j的背包中的最优解。,根据动态规划函数，用一个(n+1)(C+1)的二维表V，Vij表示把前i个物品装入容量为j的背包中获得的最大价值。,0,例如，有5个物品，其重量分别是2, 2, 6, 5, 4，价值分别为6, 3, 5, 4, 6，背包的容量为10。,按下述方法来划分阶段：第一阶段，只装入前1个物品，确定在各种情况下的背包能够得到的最大价值；第二阶段，只装入前2个物品，确定在各种情况下的背包能够得到的最大价值；依此类推，直到第n个阶段。最后，V(n,C)便是在容量为C的背包中装入n个物品时取得的最大价值。为了确定装入背包的具体物品，从V(n,C)的值向前推，如果V(n,C)V(n-1,C)，表明第n个物品被装入背包，前n-1个物品被装入容量为C-wn的背包中；否则，第n个物品没有被装入背包，前n-1个物品被装入容量为C的背包中。依此类推，直到确定第1个物品是否被装入背包中为止。由此，得到如下函数：,（式6.13）,设n个物品的重量存储在数组wn中，价值存储在数组vn中，背包容量为C，数组Vn+1C+1存放迭代结果，其中Vij表示前i个物品装入容量为j的背包中获得的最大价值，数组xn存储装入背包的物品，动态规划法求解0/1背包问题的算法如下：,第7章 贪心法,掌握贪心法的设计思想 掌握贪心法在TSP问题中的应用 掌握贪心法在背包问题中的应用 P155：实验7,贪心法的求解过程,用贪心法求解问题应该考虑如下几个方面： （1）候选集合C：为了构造问题的解决方案，有一个候选集合C作为问题的可能解，即问题的最终解均取自于候选集合C。例如，在付款问题中，各种面值的货币构成候选集合。 （2）解集合S：随着贪心选择的进行，解集合S不断扩展，直到构成一个满足问题的完整解。例如，在付款问题中，已付出的货币构成解集合。,（3）解决函数solution：检查解集合S是否构成问题的完整解。例如，在付款问题中，解决函数是已付出的货币金额恰好等于应付款。 （4）选择函数select：即贪心策略，这是贪心法的关键，它指出哪个候选对象最有希望构成问题的解，选择函数通常和目标函数有关。例如，在付款问题中，贪心策略就是在候选集合中选择面值最大的货币。 （5）可行函数feasible：检查解集合中加入一个候选对象是否可行，即解集合扩展后是否满足约束条件。例如，在付款问题中，可行函数是每一步选择的货币和已付出的货币相加不超过应付款。,贪心法的一般过程 Greedy(C) /C是问题的输入集合即候选集合 S= ; /初始解集合为空集 while (not solution(S) /集合S没有构成问题的一个解 x=select(C); /在候选集合C中做贪心选择 if feasible(S, x) /判断集合S中加入x后的解是否可行 S=S+x; C=C-x; return S; ,TSP问题,最近邻点策略：从任意城市出发，每次在没有到过的城市中选择最近的一个，直到经过了所有的城市，最后回到出发城市。,背包问题,给定n种物品和一个容量为C的背包，物品i的重量是wi，其价值为vi，背包问题是如何选择装入背包的物品，使得装入背包中物品的总价值最大?,于是，背包问题归结为寻找一个满足约束条件式7.1，并使目标函数式7.2达到最大的解向量X=(x1, x2, , xn)。,设xi表示物品i装入背包的情况，根据问题的要求，有如下约束条件和目标函数：,（式7.1）,（式7.2）,三种看似合理的贪心策略： （1）选择价值最大的物品，因为这可以尽可能快地增加背包的总价值。但是，虽然每一步选择获得了背包价值的极大增长，但背包容量却可能消耗得太快，使得装入背包的物品个数减少，从而不能保证目标函数达到最大。 （2）选择重量最轻的物品，因为这可以装入尽可能多的物品，从而增加背包的总价值。但是，虽然每一步选择使背包的容量消耗得慢了，但背包的价值却没能保证迅速增长，从而不能保证目标函数达到最大。 （3）选择单位重量价值最大的物品，在背包价值增长和背包容量消耗两者之间寻找平衡。,120 50 背包 180 190 200 (a) 三个物品及背包 (b) 贪心策略1 (c) 贪心策略2 (d) 贪心策略3,例如，有3个物品，其重量分别是20, 30, 10，价值分别为60, 120, 50，背包的容量为50，应用三种贪心策略装入背包的物品和获得的价值如图所示。,第8章 回溯法,掌握回溯法的设计思想 针对某一特定实例，会写出动态搜索过程，并画出搜索空间树，从而找到最优解 0/1背包问题 TSP问题,对于任何一个问题，可能解的表示方式和它相应的解释隐含了解空间及其大小。 例如，对于有n个物品的0/1背包问题，其可能解的表示方式可以有以下两种： （1）可能解由一个不等长向量组成，当物品i(1in)装入背包时，解向量中包含分量i，否则，解向量中不包含分量i，当n=3时，其解空间是： ( ), (1), (2), (3), (1, 2), (1, 3), (2, 3), (1, 2, 3) （2）可能解由一个等长向量x1, x2, , xn组成，其中xi=1(1in)表示物品i装入背包，xi=0表示物品i没有装入背包，当n=3时，其解空间是： (0, 0, 0), (0, 0, 1), (0, 1, 0), (1, 0, 0), (0, 1, 1), (1, 0, 1), (1, 1, 0), (1, 1, 1) ,为了用回溯法求解一个具有n个输入的问题，一般情况下，将其可能解表示为满足某个约束条件的等长向量X=(x1, x2, , xn)，其中分量xi (1in)的取值范围是某个有限集合Si=ai1, ai2, , airi，所有可能的解向量构成了问题的解空间。,问题的解空间一般用解空间树（Solution Space Trees,也称状态空间树）的方式组织，树的根结点位于第1层，表示搜索的初始状态，第2层的结点表示对解向量的第一个分量做出选择后到达的状态，第1层到第2层的边上标出对第一个分量选择的结果，依此类推，从树的根结点到叶子结点的路径就构成了解空间的一个可能解。,对于n=3的0/1背包问题，其解空间树如图8.2所示，树中的8个叶子结点分别代表该问题的8个可能解。,对于n=4的TSP问题，其解空间树如图8.3所示，树中的24个叶子结点分别代表该问题的24个可能解，例如结点5代表一个可能解，路径为12341，长度为各边代价之和。,解空间树的动态搜索,回溯法从根结点出发，按照深度优先策略遍历解空间树，搜索满足约束条件的解。在搜索至树中任一结点时，先判断该结点对应的部分解是否满足约束条件，或者是否超出目标函数的界，也就是判断该结点是否包含问题的（最优）解，如果肯定不包含，则跳过对以该结点为根的子树的搜索，即所谓剪枝（Pruning）；否则，进入以该结点为根的子树，继续按照深度优先策略搜索。,例如，对于n=3的0/1背包问题，三个物品的重量为20, 15, 10，价值为20, 30, 25，背包容量为25，从图8.2所示的解空间树的根结点开始搜索，搜索过程如下：,不可行解,再如，对于n=4的TSP问题，其代价矩阵如图8.5所示，,回溯法的求解过程,由于问题的解向量X=(x1, x2, , xn)中的每个分量xi(1in)都属于一个有限集合Si=ai1, ai2, , airi，因此，回溯法可以按某种顺序（例如字典序）依次考察笛卡儿积S1S2Sn中的元素。 初始时，令解向量X为空，然后，从根结点出发，选择S1的第一个元素作为解向量X的第一个分量，即x1= a11，如果X=(x1)是问题的部分解，则继续扩展解向量X，选择S2的第一个元素作为解向量X的第2个分量，否则，选择S1的下一个元素作为解向量X的第一个分量，即x1= a12。依此类推，一般情况下，如果X=(x1, x2, , xi)是问题的部分解，则选择Si+1的第一个元素作为解向量X的第i+1个分量时，有下面三种情况：,（1）如果X=(x1, x2, , xi1)是问题的最终解，则输出这个解。如果问题只希望得到一个解，则结束搜索，否则继续搜索其他解； （2）如果X=(x1, x2, , xi1)是问题的部分解，则继续构造解向量的下一个分量； （3）如果X=(x1, x2, , xi1)既不是问题的部分解也不是问题的最终解，则存在下面两种情况： 如果xi+1= ai1k不是集合Si1的最后一个元素，则令xi+1= ai1k1，即选择Si+1的下一个元素作为解向量X的第i+1个分量； 如果xi+1= ai1k是集合Si1的最后一个元素，就回溯到X=(x1, x2, , xi)，选择Si的下一个元素作为解向量X的第i个分量，假设xi= aik，如果aik不是集合Si的最后一个元素，则令xi= aik1；否则，就继续回溯到X=(x1, x2, , xi1)；,回溯法的一般框架迭代形式 1X= ; 2flag=false; 3k=1; 4while (k=1) 4.1 当(Sk没有被穷举)循环执行下列操作 4.1.1 xk=Sk中的下一个元素; 4.1.2 将xk加入X; 4.1.3 if (X为最终解) flag=true; 转步骤5; 4.1.4 else if (X为部分解) k=k+1; 转步骤4; 4.2 重置Sk，使得下一个元素排在第1位; 4.3 k=k-1; /回溯 5if flag 输出解X; else 输出“无解”;,回溯算法的非递归迭代形式的一般框架如下：,第9章 分支限界法,掌握分支限界法的设计思想 针对某一特定实例，会写出动态搜索过程，并画出搜索空间树，从而找到最优解 0/1背包问题 TSP问题,分支限界法首先确定一个合理的限界函数，并根据限界函数确定目标函数的界down, up 。然后，按照广度优先策略遍历问题的解空间树，在分支结点上，依次搜索该结点的所有孩子结点，分别估算这些孩子结点的目标函数的可能取值，如果某孩子结点的目标函数可能取得的值超出目标函数的界，则将其丢弃，因为从这个结点生成的解不会比目前已经得到的解更好；否则，将其加入待处理结点表（以下简称表PT）中。依次从表PT中选取使目标函数的值取得极值的结点成为当前扩展结点，重复上述过程，直到找到最优解。,解空间树的动态搜索（2）,随着这个遍历过程的不断深入，表PT中所估算的目标函数的界越来越接近问题的最优解。当搜索到一个叶子结点时，如果该结点的目标函数值是表PT中的极值（对于最小化问题，是极小值；对于最大化问题，是极大值），则该叶子结点对应的解就是问题的最优解；否则，根据这个叶子结点调整目标函数的界（对于最小化问题，调整上界；对于最大化问题，调整下界），依次考察表PT中的结点，将超出目标函数界的结点丢弃，然后从表PT中选取使目标函数取得极值的结点继续进行扩展。,例：0/1背包问题。假设有4个物品，其重量分别为(4, 7, 5, 3)，价值分别为(40, 42, 25, 12)，背包容量W=10。首先，将给定物品按单位重量价值从大到小排序，结果如下：,应用贪心法求得近似解为(1, 0, 0, 0)，获得的价值为40，这可以作为0/1背包问题的下界。 如何求得0/1背包问题的一个合理的上界呢？考虑最好情况，背包中装入的全部是第1个物品且可以将背包装满，则可以得到一个非常简单的上界的计算方法：ub=W(v1/w1)=1010=100。于是，得到了目标函数的界40, 100。 限界函数为：,分支限界法求解0/1背包问题,分支限界法求解0/1背包问题，其搜索空间如图9.1所示，具体的搜索过程如下： （1）在根结点1，没有将任何物品装入背包，因此，背包的重量和获得的价值均为0，根据限界函数计算结点1的目标函数值为1010=100； （2）在结点2，将物品1装入背包，因此，背包的重量为4，获得的价值为40，目标函数值为40 + (10-4)6=76，将结点2加入待处理结点表PT中；在结点3，没有将物品1装入背包，因此，背包的重量和获得的价值仍为0，目标函数值为10660，将结点3加入表PT中； （3）在表PT中选取目标函数值取得极大的结点2优先进行搜索；,（4）在结点4，将物品2装入背包，因此，背包的重量为11，不满足约束条件，将结点4丢弃；在结点5，没有将物品2装入背包，因此，背包的重量和获得的价值与结点2相同，目标函数值为40 + (10-4)5=70，将结点5加入表PT中； （5）在表PT中选取目标函数值取得极大的结点5优先进行搜索； （6）在结点6，将物品3装入背包，因此，背包的重量为9，获得的价值为65，目标函数值为65 + (10-9)4=69，将结点6加入表PT中；在结点7，没有将物品3装入背包，因此，背包的重量和获得的价值与结点5相同，目标函数值为40 + (10-4)464，将结点6加入表PT中；,（7）在表PT中选取目标函数值取得极大的结点6优先进行搜索； （8）在结点8，将物品4装入背包，因此，背包的重量为12，不满足约束条件，将结点8丢弃；在结点9，没有将物品4装入背包，因此，背包的重量和获得的价值与结点6相同，目标函数值为6