1、5.1.1 蛮力法的设计思想蛮力法（brute force method，也称穷举法或枚举法），是一种简单直接地解决问题的方法，采用一定的策略依次处理待求解问题的所有元素，从而找出问题的解。蛮力法的关键：依次处理所有元素（1）确定穷举的范围（2）保证处理过的元素不再被处理（为了避免陷入重复试探）用蛮力法设计的算法其时间性能往往也是最低的，典型的指数时间算法一般都是通过蛮力穷举得到的。求 an（n为非负整数）用连续整数检测算法计算GCD(m,n)5.1.1 蛮力法的设计思想用蛮力法解决问题，通常可以从两个方面进行算法设计：（1）找出枚举范围：分析问题所涉及的各种情况。（2）找出约束条件：分析问题
2、的解需要满足的条件，并用逻辑表达式表示。例：求所有的三位数，除以 11 所得的余数等于三个数字的平方和。（1）枚举范围：100 999，共 900个。（2）约束条件：设三位数是n，其百位、十位、个位的数字分别为 x，y，z。则：n%11=x2+y2+z2 注意到 x2+y2+z2 10，可以缩小枚举范围：1 x 3，0 y 3，0 z 35.1.1 蛮力法的设计思想基于以下原因，蛮力法也是一种重要的算法设计技术：（1）蛮力法不是一个最好的算法（巧妙和高效的算法很少出自蛮力），但当想不出更好的办法时，也是一种有效的解决问题的方法。（2）理论上，蛮力法可以解决可计算领域的各种问题。对于一些基本的问
3、题，蛮力法是一种常用的算法设计技术。（3）蛮力法经常用来解决一些较小规模的问题。（4）对于一些重要的问题，蛮力法可以设计一些合理的算法，这些算法具有实用价值，而且不受问题规模的限制。（5）蛮力法可以作为某类问题时间性能的下界，来衡量同样问题的其他算法是否具有更高的效率。5.1.2 一个简单的例子百元买百鸡问题【问题】已知公鸡 5 元一只，母鸡 3 元一只，小鸡 1 元三只，用 100 元钱买 100 只鸡，问公鸡、母鸡、小鸡各多少只？x+y+z=1005x+3y+z/3=1000 x 200 y 330 z 100【想法】设公鸡、母鸡和小鸡的个数为 x、y、z，则有如下方程组成立：注意到方程组
4、可能有多个解，则需要输出所有满足条件的解。5.1.2 一个简单的例子百元买百鸡问题算法：百元买百鸡问题输入：100元钱，100只鸡输出：所有可行解 1.初始化解的个数 count=0；2.循环变量 x 从 020 循环执行下述操作：2.1 循环变量 y 从 033 循环执行下述操作：2.1.1 z=100 x y；2.1.2 如果 5*x+3*y+z/3 等于 100，则 count+；输出 x、y和z的值；2.1.3 y+；2.2 x+；3.如果 count 等于 0，则输出无解信息；【算法】设变量 x 表示公鸡的个数，y 表示母鸡的个数，z 表示小鸡的个数，count表示解的个数，算法如下
5、：void Chicken()int x,y,z,count=0;for(x=0;x=20;x+)for(y=0;y=33;y+)z=100-x-y;/满足共100只 if(z%3=0)&(5*x+3*y+z/3=100)/满足总价 count+;/解的个数加1 cout公鸡：x母鸡：y小鸡：zendl;if(count=0)cout问题无解 0&ri!=k)i-;return i;【算法实现 1】将查找集合存储在数组r1 rn中，下标 i 初始化在数组的高端，注意在查找过程中要检测比较位置是否越界，程序如下：5.2.1 顺序查找【问题】在一个整数集合中查找值为 k 的元素。【想法 2】为了避
6、免在查找过程中每一次比较后都要判断查找位置是否越界，可以设置观察哨（sentinel），即将待查值放在查找方向的“尽头”处，则比较位置i至多移动到下标0处，也就是“哨兵”的位置。i 25 10 15 24 6 12 35 40 98 550 1 2 3 4 5 6 7 8 9 例：查找 25【算法实现 2】设函数SeqSearch2实现改进的顺序查找算法，程序如下：查找方向int SeqSearch2(int r,int n,int k)int i=n;data0=k;while(datai!=k)i-;return i;5.2.1 顺序查找【算法分析】算法SeqSearch1的时间主要耗费在
7、条件表达式(i 0&ri!=k)，算法SeqSearch2的时间主要耗费在条件表达式(ri!=k)，设 pi 表示查找第 i 个元素的概率，等概率情况下，执行次数为：算法SeqSearch1要执行两个判断，而算法SeqSearch2只执行一个判断。实验表明，表长大于1000时，改进算法进行一次顺序查找的时间几乎减少一半。5.2.2 串匹配问题5.2.2 串匹配问题5.2.2 串匹配问题串匹配（模式匹配）：在主串 S 中寻找子串 T 的过程S=s1 s2 sn T=t1 t2 tm如果匹配成功，返回 T 在 S 中的位置；否则返回 0串匹配问题有什么特点？（2）算法改进所取得的积累效益：串匹配操
8、作经常被调用，执行频率高（1）算法的一次执行时间：问题规模通常很大，常常在大量信息中进行匹配5.2.2 串匹配问题【问题】给定两个字符串 S 和 T，在主串 S 中查找子串 T 的过程称为串匹配（string matching，也称模式匹配），T 称为模式。【想法 1】从主串 S 的第一个字符开始和模式 T 的第一个字符进行比较，若相等，则继续比较两者的后续字符；若不相等，则从主串 S 的第二个字符开始和模式 T的第一个字符进行比较，重复上述过程，若 T 中的字符全部比较完毕，则说明本趟匹配成功；若 S 中的字符全部比较完毕，则匹配失败。这个算法称为BF算法。jiij 主串 Ss1 s2 si
9、 sn模式 T t1 t2 tjij5.2.2 串匹配问题例：主串 S=ababcabcacbab，模式 T=abcaca b a b c a b c a c b a bi=2，j=2失败；i 回溯到 1，j 回溯到 0ijijij第 1趟a b c a c 5.2.2 串匹配问题例：主串 S=ababcabcacbab，模式 T=abcaca b a b c a b c a c b a bi=2，j=2失败；i 回溯到 1，j 回溯到 0i第 2趟ja b c a c 5.2.2 串匹配问题例：主串 S=ababcabcacbab，模式 T=abcaca b a b c a b c a c
10、b a bi第 2趟ja b c a c i=1，j=0失败i 回溯到 2，j 回溯到 05.2.2 串匹配问题例：主串 S=ababcabcacbab，模式 T=abcaca b a b c a b c a c b a b第 3趟ija b c a c iji=6，j=4失败i 回溯到 3，j 回溯到 05.2.2 串匹配问题例：主串 S=ababcabcacbab，模式 T=abcaca b a b c a b c a c b a b第 4趟ija b c a c i=3，j=0失败i 回溯到 4，j 回溯到 05.2.2 串匹配问题例：主串 S=ababcabcacbab，模式 T=ab
11、caca b a b c a b c a c b a b第 5趟ija b c a c i=4，j=0失败i 回溯到 5，j 回溯到 05.2.2 串匹配问题例：主串 S=ababcabcacbab，模式 T=abcaca b a b c a b c a c b a b第 6趟ija b c a c i=10，j=5，T中全部字符都比较完毕，匹配成功ijijijijijij算法：串匹配算法BF输入：主串 S，模式 T输出：T 在 S 中的位置 1.初始化主串比较的开始位置 index=0;2.在串 S 和串 T 中设置比较的起始下标 i=0,j=0；3.重复下述操作，直到 S 或 T 的所有字
12、符均比较完毕：3.1 如果Si 等于 Tj，则继续比较 S 和 T 的下一对字符；3.2 否则，下一趟匹配的开始位置 index+，回溯下标 i=index，j=0；4.如果 T 中所有字符均比较完，则返回匹配的开始位置；否则返回0；【算法 1】设字符数组 S 存放主串，字符数组 T 存放模式，BF算法如下：【算法分析 1】设匹配成功发生在 si 处，则最坏情况下：)(2)2()(11)(1111nmOmnmmimnmipmnimnii5.2.2 串匹配问题int BF(char S,char T)int index=0,i=0,j=0;while(Si!=0)&(Tj!=0)if(Si=Tj
13、)i+;j+;else index+;i=index;j=0;/i 和 j 分别回溯 if(Tj=0)return index+1;else return 0;【算法实现 1】设字符数组 S 存放主串，字符数组 T 存放模式，BF算法如下：5.2.2 串匹配问题5.2.2 串匹配问题【问题】给定两个字符串 S 和 T，在主串 S 中查找子串 T 的过程称为串匹配（string matching，也称模式匹配），T 称为模式。【想法 2】KMP 算法对于 BF 算法进行了很大改进，基本思想是主串不进行回溯，模式 T 要回溯到某一个字符。jiij 主串 Ss1 s2 si sn模式 T t1 t2
14、 tj在每趟匹 配不成功时存在大量回溯，没有利用已经部分匹配的结果5.2.2 串匹配问题如何在匹配不成功时主串不回溯？i 主串 Ss1 s2 si sn模式 T t1 t2 tj如何确定模式的滑动距离？主串不回溯，模式就需要向右滑动一段距离5.2.2 串匹配问题a b a b c a b c a c b a bij第 1趟a b c a c i=2，j=2失败；s1=t1;t0t1t0s1a b a b c a b c a c b a b第 2趟a b c a c 5.2.2 串匹配问题a b a b c a b c a c b a bij第 1趟a b c a c i=2，j=2失败；s1=
15、t1;t0t1t0s1a b a b c a b c a c b a bi第 3趟ja b c a c 5.2.2 串匹配问题a b a b c a b c a c b a b第 3趟a b c a c iji=6，j=4失败 s3=t1;t0t1t0s3a b a b c a b c a c b a b第 4趟a b c a c 5.2.2 串匹配问题a b a b c a b c a c b a b第 3趟a b c a c iji=6，j=4失败 s4=t2;t0t2t0s4a b a b c a b c a c b a b第 5趟a b c a c 5.2.2 串匹配问题a b a b
16、 c a b c a c b a b第 3趟a b c a c iji=6，j=4失败 s4=t2;t0t2t0s4a b a b c a b c a c b a b第 6趟a b c a c iji=6，j=4失败s5=t3;t0=t3t0=s55.2.2 串匹配问题结论：i 可以不回溯，模式向右滑动到新的比较起点 k如何由当前部分匹配结果确定模式向右滑动的新比较起点 k？a b a b c a b a b c a c ija b c a c a b a b c a b ik下一趟（1）T0Tk-1=Si-kSi-15.2.2 串匹配问题结论：i 可以不回溯，模式向右滑动到新的比较起点 k如
17、何由当前部分匹配结果确定模式向右滑动的新比较起点 k？a b a b c a b a b c a c ija b c a c a b a b c a b ik下一趟（1）T0Tk-1=Si-kSi-1（2）Tj-kTj-1=Si-kSi-1 T0Tk-1=Tj-kTj-15.2.2 串匹配问题长度为 k 的前缀（1）k 与 j 具有函数关系，由当前失配位置 j，可以计算出滑动位置 kT0 Tk-1=Tj-k Tj-1 说明了什么？T0 Tk-1=Tj-k Tj-1 的物理意义是什么？长度为 k 的后缀T0 Tj中前缀和后缀相等的真子串唯一吗?（2）滑动位置 k 仅与模式串 T 有关a b a
18、b a c a b a b a c a b a b a c k=1k=35.2.2 串匹配问题max k|1kj 且且T0 Tk-1=Tj-k Tj-1模式应该向右滑多远才能保证算法的正确性?a b a b a b a cija b a b a ca b a b a b a cija b a b a ca b a b a b a ca b a b a cijk=1:k=3:5.2.2 串匹配问题-1 j=0maxk|1kj 且且T0 Tk-1=Tj-k Tj-1 集合非空0 其它情况nextj=设nextj表示在匹配过程中与Tj比较不相等时，下标 j 的回溯位置 下标：0 1 2 3 4 模
19、式 串 T：a b a b c k=nextj：j=0时,k-1j=1时,k0-10j=2时,T0T1，因此，k=00j=3时,T0T2，T0T1 T1T2，因此，k=11j=4时,T0 T3，T0T1=T2T3，T0T1T2T1T2T3，因此，k=225.2.2 串匹配问题 a b a b a a b a b c b i=4，j=4失败；j=next4=2ij第 1趟 a b a b cnextj=-1,0,0,1,2 a b a b a a b a b c b ij第 2趟 a b a b c5.2.2 串匹配问题 a b a b a a b a b c b 第 2趟 a b a b ci
20、=5，j=3失败；j=next3=1ij a b a b a a b a b c b 第 3趟 a b a b cijnextj=-1,0,0,1,25.2.2 串匹配问题 a b a b a a b a b c b 第 3趟 a b a b ci=5，j=1失败；j=next1=0ij a b a b a a b a b c b 第 4趟 a b a b cijnextj=-1,0,0,1,2算法：串匹配算法KMP输入：主串 S，模式 T输出：T 在 S 中的位置 1.在串 S 和串 T 中分别设置比较的起始下标 i=0,j=0；2.重复下述操作，直到 S 或 T 的所有字符均比较完毕：2.
21、1 如果 Si 等于 Tj，则继续比较 S 和 T 的下一对字符；2.2 否则，将下标 j 回溯到 nextj 位置，即 j=nextj；2.3 如果 j 等于-1，则将下标 i 和 j 分别加 1，准备下一趟比较；3.如果 T 中所有字符均比较完毕，则返回本趟匹配的开始位置；否则返回0；【算法 2】设字符数组 S 存放主串，字符数组 T 存放模式，在求得了模式 T 的next值后，KMP算法如下：【算法分析 2】在求得模式 T 的 next 值后，KMP算法只需将主串扫描一遍，设主串的长度为 n，则KMP算法的时间复杂度是O(n)。5.2.2 串匹配问题void GetNext(char T
22、,int next)int i,j,len;next0=-1;for(j=1;Tj!=0;j+)/依次求nextj for(len=j-1;len=1;len-)/相等子串的最大长度为j-1 for(i=0;i len;i+)/比较T0Tlen-1与Tj-lenTj-1 if(Ti!=Tj-len+i)break;if(i=len)nextj=len;break;if(len 1)nextj=0;/其他情况，无相等子串 【算法实现 2】设字符数组 S 存放主串，字符数组 T 存放模式，设函数GetNext用蛮力法求得模式T的next值，函数KMP实现KMP算法，程序如下：5.2.2 串匹配问题
23、int KMP(char S,char T)/求T在S中的序号 int i=0,j=0,next80;/假定模式最长为80个字符 GetNext(T,next);while(Si!=0&Tj!=0)if(Si=Tj)i+;j+;else j=nextj;if(j=-1)i+;j+;if(Tj=0)return(i-j+1);/返回本趟匹配的开始位置 else return 0;5.2.2 串匹配问题【算法实现 2】设字符数组 S 存放主串，字符数组 T 存放模式，设函数GetNext用蛮力法求得模式T的next值，函数KMP实现KMP算法，程序如下：v第 5 章 蛮力法5-3 排序问题中的蛮力
24、法5.3.1 选择排序【问题】选择排序（selection sort）的基本思想是：第 i 趟排序在无序序列 ri rn中找到值最小的记录，并和第 i 个记录交换作为有序序列的第 i 个记录。有序区无序区minr1ri-1rirnr1ri-1riri+1rn【想法】选择排序的一个例子（无序区用方括号括起来）：5.3.1 选择排序2420101812待排序序列第一趟排序结果第二趟排序结果第三趟排序结果第四趟排序结果1012242018122420181018241220102018241210【算法实现】设数组 rn 存储待排序记录序列，注意到数组下标从 0 开始，则第 i 个记录存储在 ri-
25、1 中。程序如下：5.3.1 选择排序void SelectSort(int r,int n)int i,j,index,temp;for(i=0;i n-1;i+)/进行n-1趟选择排序 index=i;for(j=i+1;j n;j+)/在无序区中查找最小记录 if(rj rindex)index=j;temp=ri;ri=rindex;rindex=temp;/交换记录 时间复杂度？2122010(1)1(1)()2nnnij iin nn iO n 5.3.2 起泡排序【问题】起泡排序（bubble sort）的基本思想是：两两比较相邻记录，如果反序则交换，直至没有反序的记录。【想法】
26、起泡排序的一个例子（无序区用方括号括起来）：无序区r1r2ri-1有序区rirnri+1反序则交换类似水中的气泡，体积大的浮到上面，起泡排序因而得名5.3.2 起泡排序2420101812待排序序列第一趟排序结果第二趟排序结果第三趟排序结果第四趟排序结果1210201824241012182024101218202410121820第二趟排序有必要吗？88888第五趟排序结果24101218208第四趟排序有必要吗？5.3.2 起泡排序2420101812待排序序列第一趟排序结果第二趟排序结果第三趟排序结果1210201824241012182024101218208888一趟起泡排序可以确定
27、多个记录的最终位置一趟起泡排序没有记录交换，则结束排序过程【算法实现】设数组 rn 存储待排序记录序列，在一趟起泡排序过程中，如果没有交换记录操作，则表明序列已经有序。程序如下：void BubbleSort(int r,int n)int j,temp,bound,exchange=n-1;/第一趟排序区间0,n-1 while(exchange!=0)/当上一趟排序有记录交换时 bound=exchange;exchange=0;for(j=0;j rj+1)temp=rj;rj=rj+1;rj+1=temp;exchange=j;/记载每一次记录交换的位置 时间复杂度？最好？最坏？平均？
28、5.3.2 起泡排序【算法实现】两个起泡排序的程序比较，程序如下：void BubbleSort(int r,int n)int j,temp,bound,exchange=n-1;while(exchange!=0)bound=exchange;exchange=0;for(j=0;j rj+1)temp=rj;rj=rj+1;rj+1=temp;exchange=j;5.3.2 起泡排序void BubbleSort1(int r,int n)int i,j,temp;for(i=0;i n-1;i+)for(j=0;j rj+1)temp=rj;rj=rj+1;rj+1=temp;用蛮力
29、法设计的算法，一般来说，都可以对算法的第一个版本进行一定程度的改良，改进其时间性能，但只能减少系数，而数量级不会改变。v第 5 章 蛮力法5-4 图问题中的蛮力法5.4.1 哈密顿回路问题【问题】著名的爱尔兰数学家哈密顿（William Hamilton）提出的周游世界问题。假设正十二面体的 20 个顶点代表 20 个城市，哈密顿回路问题（Hamilton cycle problem）要求从一个城市出发，经过每个城市恰好一次，然后回到出发城市。【想法】蛮力法求解哈密顿回路的基本思想是，对于给定的无向图 G=(V,E)，依次考察图中所有顶点的全排列，满足以下两个条件的全排列(vi1,vi2,vi
30、n)构成的回路就是哈密顿回路：（1）(vij,vij+1)E（1jn-1）（2）(vin,vi1)E5.4.1 哈密顿回路问题【想法】依次考察图中所有顶点的全排列，满足（1）(vij,vij+1)E（1 j n-1）（2）(vin,vi1)E 的全排列(vi1,vi2,vin)构成的回路就是哈密顿回路。5.4.1 哈密顿回路问题【算法】蛮力法求解哈密顿回路的算法用伪代码描述如下：算法：哈密顿回路HamiltonCycle输入：无向图 G=(V,E)输出：如果存在哈密顿回路，则输出该回路，否则，输出无解信息 1.对顶点集合1,2,n的每一个排列 vi1vi2vin 执行下述操作：1.1 循环变量
31、 j 从 1n-1 重复执行下述操作：1.1.1 如果顶点 vij 和 vij+1 之间不存在边，则转步骤 1 考察下一个排列；1.1.2 否则 j+;1.2 如果 vin 和 vi1 之间存在边，则输出排列 vi1vi2vin，算法结束；2.输出无解信息；【算法分析】算法HamiltonCycle在找到一条哈密顿回路后，即可结束算法。但是，最坏情况下需要考察顶点集合的所有全排列，时间复杂度为O(n!)。5.4.2 TSP问题【问题】TSP问题（traveling salesman problem）是指旅行家要旅行 n 个城市然后回到出发城市，要求各个城市经历且仅经历一次，并要求所走的路程最短
32、。【想法】蛮力法求解 TSP问题的基本思想是，找出所有可能的旅行路线，即依次考察图中所有顶点的全排列，从中选取路径长度最短的哈密顿回路。5.4.2 TSP问题【算法】蛮力法求解 TSP问题与求解哈密顿回路问题类似，不同的仅是将回路经过的边上的权值相加得到相应的路径长度，具体算法请读者自行设计。【算法分析】蛮力法求解 TSP问题必须依次考察顶点集合的所有全排列，从中找出路径长度最短的简单回路，因此，时间下界是(n!)。除了该问题的一些规模非常小的实例，蛮力法几乎是不实用的。随着城市数量的增长，TSP问题的可能解也在迅速地增长。例如：10 城市的 TSP问题有大约 180 000 个可能解；20
33、城市的 TSP问题有大约 60 000 000 000 000 000 个可能解；50 城市的 TSP问题有大约 1062 个可能解。v第 5 章 蛮力法5-5 几何问题中的蛮力法5.5.1 最近对问题【问题】最近对问题（nearest points problem）要求在包含n个点的集合中找出距离最近的两个点。严格地讲，距离最近的点对可能多于一对，简单起见，只找出其中的一对即可。【想法】简单起见，只考虑二维的情况，分别计算每一对点之间的距离，然后找出距离最小的那一对。为了避免对同一对点计算两次距离，可以只考虑 ij 的点对(pi,pj)。假设所讨论的点以标准笛卡儿坐标形式给出，两个点 pi=
34、(xi,yi)和 pj=(xj,yj)之间的距离是欧几里得距离，在求欧几里得距离时，可以免去求平方根操作。5.5.1 最近对问题【算法实现】设数组 xn 和 yn 存储 n 个点的坐标，函数ClosestPoints的形参index1 和 index2 接收最近点对的下标，假设最大距离不超过 1000，程序如下：int ClosestPoints(int x,int y,int n,int&index1,int&index2)int i,j,d,minDist=1000;for(i=0;i n-1;i+)for(j=i+1;j n;j+)/只考虑ij的点对 d=(xi-xj)*(xi-xj)+
35、(yi-yj)*(yi-yj);if(d minDist)minDist=d;index1=i;index2=j;return minDist;时间复杂度？111112)()1()(22)(ninijninOnninnT5.5.2 凸包问题定义5.1 对于平面上若干个点构成的有限集合，如果以集合中任意两点 P 和 Q 为端点的线段上的点都属于该集合，则称该集合是凸集合（convex set）。定义5.2 一个点集 S 的凸包（convex hull）是包含 S 的最小凸集合，其中，最小是指 S 的凸包一定是所有包含 S 的凸集合的子集。最小凸多边形上的点称为凸包的极点（extreme dot）
36、。【问题】凸包问题（convex hull problem）要求为平面上具有 n 个点的集合S构造最小凸多边形。【想法】设经过集合 S 中两个点(xi,yi)和(xj,yj)的线段是 lij，如果该集合中的其他点都位于线段 lij 的同一侧（假定不存在三点同线），则线段 lij 是该集合凸包边界的一部分。在平面上，经过两个点(xi,yi)和(xj,yj)的直线定义如下：这条直线把平面分成两个半平面：其中一个半平面中的点都满足Ax+By+C0，另一个半平面中的点都满足Ax+By+C0。5.5.2 凸包问题【算法】对于点集 S 中每一对顶点构成的线段，依次检验其余点是否位于这条线段的同一边，由于线
37、段构成了凸包的边界，则满足条件的所有线段就构成了该凸包的边界。为了避免重复检验同一点对构成的线段，只考虑 ij 的点对(pi,pj)。5.5.2 凸包问题int BulgePack(int x,int y,int n,int px,int py)int i,j,k,sign1,sign2;int A,B,C,index=0;for(i=0;i n-1;i+)for(j=i+1;j n;j+)【算法实现】设数组 xn 和 yn 存储 n 个点的坐标，数组 pxn 和 pyn 存储所有极点的坐标，变量 sign1 和 sign2 表示两个半平面，函数BulgePack的返回值是极点的个数。程序如下
38、：sign1=0;sign2=0;/初始化sign1和sign2 A=yi yj;B=xj xi;C=xi*yj xj*yi;for(k=0;k 0)sign1=1;else sign2=1;if(sign1=sign2)break;/两个半平面均有点 if(k=n)/点i和j是极点 pxindex=xi;pyindex+=yi;pxindex=xj;pyindex+=yj;return index;5.5.2 凸包问题时间复杂度？O(n2)v第 5 章 蛮力法5-6 拓展与演练5.6.1 KMP算法中next值的计算设模式的长度为 m，用蛮力法求解 KMP算法中的 next 值时，最坏情况下
39、的时间代价是：实际上，只需将模式扫描一遍，能够在线性时间内求得模式的 next 值。121(1)(2)(1)()2mjmmjO m假设已经计算出 next0，next1，nextj，如何计算 nextj+1 呢？5.6.1 KMP算法中next值的计算设 k=nextj，则 T0Tk-1=Tj-kTj-1，为了计算 nextj+1，比较Tk 和 Tj，可能出现两种情况：（1）Tk=Tj：说明 T0Tk-1Tk=Tj-kTj-1Tj，则 nextj+1=k+1；5.6.1 KMP算法中next值的计算（2）TkTj：此时要找出 T0Tj-1 的真前缀和真后缀相等的第 2 大子串。令 k=next
40、k，再比较 Tk 和 Tj，此时会出现两种情况：Tk=Tj，与情况（1）类似，nextj+1=k+1；TkTj，与情况（2）类似，再找出 T0Tk-1 的真前缀和真后缀相等的最大子串，重复（2）的过程，直至 Tk=Tj，或 nextk=-1，说明 T0Tj-1 不存在真前缀和真后缀相等的子串，此时，nextj+1=0。5.6.1 KMP算法中next值的计算例如，模式T=abaababc的next值计算如下：j=0 时，next0=-1j=1 时，k=next0=-1，next1=0j=2 时，k=next1=0，T0T1；k=nextk=next0=-1，next2=0j=3 时，k=nex
41、t2=0，T0=T2，next3=k+1=0+1=1j=4 时，k=next3=1，T1T3；k=nextk=next1=0，T0=T3，next4=k+1=1j=5 时，k=next4=1，T1=T4，next5=k+1=1+1=2j=6 时，k=next5=2，T2=T5，next6=k+1=2+1=3j=7 时，k=next6=3，T3T6；k=nextk=next3=1，T1=T6，next7=k+1=2【算法实现】在线性时间内求得模式next值的程序如下：void GetNext(char T,int next)int j=0,k=-1;next0=-1;while(Tj!=0)/对
42、模式T扫描一遍 if(k=-1)next+j=0;k=0;/无相同子串 else if(Tj=Tk)/确定nextj+1的值 k+;next+j=k;/相等子串长度加1 else k=nextk;/取T0Tj下一个相等子串的长度 5.6.1 KMP算法中next值的计算5.6.2 0/1背包问题【问题】给定n个重量为w1,w2,wn、价值为v1,v2,vn的物品和一个容量为C的背包，0/1背包问题（0/1 knapsack problem）是求这些物品的一个最有价值的子集，并且要能够装到背包中。【想法】考虑给定n个物品集合的所有子集，找出所有总重量不超过背包容量的子集，计算每个可能子集的总价值
43、，然后找到价值最大的子集。例如，给定4个物品的重量为7,3,4,5，价值为42,12,40,25，和一个容量为10的背包，求解过程如下。5.6.2 0/1背包问题算法：蛮力法求解 0/1背包问题输入：重量w1,w2,wn，价值v1,v2,vn，背包容量C输出：装入背包的物品编号 1.初始化最大价值maxValue=0；结果子集S=；2.对集合1,2,n的每一个子集T，执行下述操作：2.1 初始化背包的价值value=0；背包的重量weight=0;2.2 对子集 T 的每一个元素 j 执行下述操作：2.2.1 如果weight+wj C，则weight=weight+wj；value=value+vj;2.2.2 否则，转步骤 2 考察下一个子集；2.3 如果maxValue value，则maxValue=value;S=T;3.输出子集 S 中的各元素；【算法】蛮力法求解 0/1背包问题的算法用伪代码描述如下：
