算法设计与分析开卷.doc

算法(Algorithm)有限性：每条指令的执行次数、时间有限；确定性：每条指令有确定的含义、无歧义；输入：0个或多个输入；输出：1个或多个输出；有效性。程序：是算法用某种程序设计语言的具体实现。程序可以不满足算法的有限性。算法涵盖的主要元素：数据、运算 设计算法的基本原则：自顶向下逐步求精。 设计算法的基本过程：分析问题域，确定数学模型；整理初始状态与结果状态之间的隐含关系，寻求从数学模型已知初始状态到达结果状态的运算步骤。抽象数据类型（ADT）= 数学模型+运算 ADT=(D,S,P)数据对象、数据关系、基本操作算法复杂性是算法运行所需要的计算机资源量，时间资源量称为时间复杂性，空间资源量称为空间复杂性。这些量只依赖于算法所要求解问题的规模、算法的输入和算法本身。空间复杂性的组成：指令空间(编译之后的程序指令)数据空间(常量、变量)栈空间(函数调用)指令空间的大小对特定问题不敏感。 算法分析方法：概率分析；分摊分析；实验分析分治算法能解决问题特征：缩小问题规模可以降低解决问题的难度；可以将子问题的解合并为原问题解；问题分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。替换方法解递归方程步骤：猜测出递归解的形式；用数学归纳法找出使解真正有效的常数递归树方法基本步骤：利用递归树推测出一个解；利用替换方法进行证明分治算法的特征：将较大规模的问题分解为若干个较小规模的子问题，每个子问题的求解过程与原问题一样，并利用自底向上的求解策略得到最终的解。直接或间接地调用自身的算法称为递归算法。在定义函数时调用到函数自身称为递归函数。边界条件与递归方程是递归函数的二要素。递归优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。缺点：递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。贪心算法设计思路：总是做出在当前看来最好的选择，即贪心算法并不是从整体最优考虑，它所做的选择只是在某种意义上的局部最优选择。前提：贪心选择性质和最优子结构性质。所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。贪心算法与动态规划算法的差异：动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每做一次贪心选择就将所求问题简化为规模更小的子问题。背包、活动安排、最优装载、单源最短路径问题。一、算法时间复杂性问题1. 试证明下面的定理：(1)如果f(n)=O(s(n)并且g(n)=O(r(n),则f(n)+g(n)=O(s(n)+r(n);(2)如果f(n)=O(s(n)并且g(n)=O(r(n),则f(n)*g(n)=O(s(n)*r(n)根据符号O的定义，存在正常数C1，C2和自然数N1,N2，使得对所有的n= N1，f（n）= N2,g(n) =C2r(n)所以 f（n）+ g(n) = C1s(n)+ C2r(n)，f（n）*g(n)= C1C2s(n)r(n)；令 C3=max（C1,C2），C4=C1*C2；则：f（n）+ g(n) = C3s(n)+ r(n)=O(s(n)+ r(n) f（n）*g(n) = C4*s(n)*r(n)=O(s(n)* r(n)2. 假设某算法在输入规模为n时的计算时间为：T（n）=3*2n ，在A型计算机上实现并完成该算法的时间为t秒，现有更先进的B型计算机，其运算速度为A型计算机的64倍。试求出若在先进的B型机上运行同一算法在则T秒内能求解输入规模为多大的问题？某台t秒内完成的基本运算的次数=3*2n新机器t秒内完成的基本运算的次数=64*3*2n=26*3*2n=3*2(n+6)设N为B型机上t秒钟能求解的问题的规模所以T=T(N)=3*2N=3*2(n+6) 则：N=n+6 3. 试说明为什么“在现代计算机上运行指数（如2n）时间算法是不可能的，要想在顺序处理机上扩大所处理问题的规模，有效的途径是降低算法计算复杂度的数量级，而不是提高计算机的速度”。(1)(log2n)(n)(nlog2n)(n2)(nn)一个计算时间为(1)的算法，它的基本运算执行的次数是固定的，因此，总的时间由一个常数(即，零次多项式)来限界，而一个时间为(n2)的算法则由一个二次多项式来限界。以下六种计算时间的多项式时间算法是最为常见的，其关系为(2n)(n!)(nn)指数时间算法一般有(2n)、(n!)和(nn)等。其关系为：其中，最常见的是时间为(2n)的算法。当n取得很大时，指数时间算法和多项式时间算法在所需时间上非常悬殊因为根本就找不到一个这样的m，使得2n囿界于nm。换言之，对于任意的m0，总可以找到n0，当nn0时，有2nnm。因此，只要有人能将现有指数时间算法中的任何一个算法简化为多项式时间算法，那就取得了一个伟大的成就。(log2n)、(n)和(nlog2n)比另外三种时间函数的增长率慢得多。 由这些结果可看出，当数据集的规模(即n的取值)很大时，要在现代计算机上运行具有比(nlog2n)复杂度还高的算法往往是很困难的。尤其是指数时间算法，它只有在n值取得非常小时才实用。尽管通过提高计算机的速度比之前快1000倍，甚至10000倍，但当指数规模的n足够大时，n每增加1，1000倍的提速即可瞬间化为乌有，所以要想在顺序处理机上扩大所处理问题的规模，有效的途径是降低算法的计算复杂度的数量级，而不是提高计算机的速度。2、 简答1. 对计算复杂性的研究能够使人们弄清所求解问题的固有难度，并得出评价某类算法优劣的准则，用以指导设计出更高效的算法。试用简短的语言说明“建立一个问题复杂性的下界要比确定它的上界困难得多！”其复杂性上界是已知求解该问题的最快算法的费用，而复杂性下界只能通过理论证明来建立。寻求某个问题的计算复杂性上界，只要研究一个算法的复杂性即可。但是要寻求同一问题的计算复杂性下界，则必须考察所有的解决该问题的算法，证明一个问题的复杂性下界就需要证明不存在任何复杂性低于下界的算法。显然，建立下界要比确定上界困难得多。2. 满足何种性质的问题被称为NP完全问题？请简述研究NP完全问题的意义；（1）NP即是多项式复杂程度的非确定性问题。 而如果任何一个NP问题都能通过一个多项式时间算法转换为某个NP问题，那么这个NP问题就称为NP完全问题。如果一个NP完全问题能在多项式时间内得到解决，那么NP中的每一个问题都可以在多项式时间内解决。（2）NP完全是指这样一类NP问题,所有的NP问题都可以用多项式时间划归到他们中的一个.所以显然NP完全的问题具有如下性质:它可以在多项式时间内求解，当且仅当所有的其他的NP完全问题也可以在多项式时间内求解。这样一来,只要我们找到一个NPC问题的多项式解,所有的NP问题都可以多项式时间内划归成这个NPC问题,再用多项式时间解决,这样NP就等于P了.NP完全性理论的重要性:知道一个问题是NP完全的就给我们提供了有价值的信息，告诉我们采用什么样的途径可以是最富有成效的。一定不要去优先寻找有效的、精确的算法。现在比较适当的途径是集中精力致力于其他较低目标的方法。例如，你可以寻找解决这个问题的各种特殊情况的有效算法。寻找在大多数情况下看来能快速运算的算法，虽然不能保证它在任何情况下都能快速地运算。或者你甚至可以放松问题的某些方面，寻找一个只能给出满足大部分要求的快速算法。简言之，NP完全性理论的初步应用是帮助算法设计人员找到最有可能得到有用的算法的努力方向3. “当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质”。问题的最优子结构性质是该问题可用动态规划算法求解的基本要素，试简要阐述“论证某一问题的最优子结构性质”时的一般方法；矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。在分析问题的最优子结构性质时，所用的方法具有普遍性：首先假设由问题的最优解导出的子问题的解不是最优的，然后再设法说明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾。利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。最优子结构是问题能用动态规划算法求解的前提。同一个问题可以有多种方式刻划它的最优子结构，有些表示方法的求解速度更快（空间占用小，问题的维度低）例如：假设（y1,y2,yn）是0-1背包问题的一个最优解，而（y2,yn）是相应子问题的一个最优解，有 假设（y2,yn）不是一个最优解，而（z2,zn）是最优解，由此可知，这说明（y1,z1,z2,zn）是问题的整体最优解，与（y1,y2,yn）是最优解矛盾，所以证明了最优子结构性质！三、算法设计与分析问题1. 最大值和最小值问题的最优算法（18）给定n个实数存放于一维数组A中，试设计一个算法在最坏情况下用3n/2-2次的比较找出A中的最大值和最小值（为简化，可假设n为偶数）。2. 社会名流问题在 n个人中，一个被所有人知道但却不知道别人的人，被定义为社会名流。现在的问题是如果存在，试找出该社会名流。你可以使用的唯一方式是询问：“对不起，请问你知道那个人吗？”（假定所有回答都正确，甚至这位社会名流也将回答。）我们的最终目标是将询问的数目最小化。给定一个nn邻接矩阵，确定是否存在一个i，其满足在第i列所有项（除了第ii项）都为1，并且第i行所有项（除了第ii项）都为0。大致的算法思路：随便取一个非对角线元素比如Arrayij，如果Arrayij=0成立，则j不是社会名流，于是删去第j行和第j列。同样，如果Arrayij=1成立，则删去第i行和第i列；总之，无论对应项取何值，都可以删去一行和一列，因此整个操作只耗费O(n)的时间。重复此操作直至剩下最后一个元素。最后，检验该元素是否为社会名流即可。如果该元素不是，则该群人中不存在社会名流。3.数列极差问题 在黑板上写了N个正数组成的一个数列，进行如下的操作：每一次任选其中的两个数设为a和b，将其擦去，然后在数列中加入一个新的数a*b+1，如此下去直至黑板上只剩下一个数为止。在所有按这种操作方式最后得到的数中，最大的数记为Max，最小的数记为Min，则该数列的极差定义为M=Max-Min。贪心算法最重要的两个性质是：贪心选择性质和最优子结构性质。贪心选择性质是所求问题的整体最优解可以通过一系列局部最优的选择，也就是贪心选择来达到。而最优子结构性质是指一个问题的最优解包含其子问题的最优解。 问题的关键就是MAX MIN值的求解问题，所以首先看下怎么样来求MAX MIN值。设有三个数x y z,且xynum2num3。所以我们可以得出结论：优先选择数列中最小的2个数进行（a*b+1）运算得到的值大，优先选择数列中最大的2个数进行（a*b+1）运算得到的值小。我们可以把整体的MAX，MIN值通过一系列局部求MAX,MIN值来求我们想要的结果。 我们再看下用贪心策略求解的合理性：假设经（N3）次运算后得到3个数：x y max（maxxy），其中max是（N2）个数经（N3）次运算后所得的最大值，此时最大值m （x*y1）max1。若经（N2）次变换后所得的3个数为：x y z（zxy）且z不为（N2）次变换后的最大值，即zmax则所求得的最大值为： m（x*y+1）*z+1， 此时mm（1+x*y）（maxz）0 所以此时不为最优解。 所以若使第k（1kN1）次变换后所得值最大，必使（k1）次变换后所得值最大（符合贪心策略的最优子结构性质），在进行第k次变换时，只需取在进行（k1）次变换后所得数列中的两最小数x，y进行运算，再把结果插入到数列即可。所以综上所述：该算法可以简单的描述为：MAX：不断地取当前黑板上的两个最小的数进行运算并且放回，会使最后的结果最大。MIN：不断地取当前黑板上的两个最大的数进行运算并且放回，会使最后的结果最小。数列极差就是：MAX-MIN！算法设计： 先将数列an按从小到大进行排列(快速排序) 进行最大值的计算：选出an中最小的两个数进行（a*b+1）运算，在把运算结果按从小到大插入到数列中。一直这样运算，最后就可以得出MAX值。 进行最小值的计算：选出an中最大的两个数进行（a*b+1）运算，在把运算结果按从小到大插入到数列中。一直这样运算，最后就可以得出MIN值。 最后该数列的极差M =MAX-MIN4. 试说明如何修改快速排序算法，使它在最坏情况下的计算时间为O(nlgn)。可以通过减少递归栈的使用进行优化，快速排序的实现需要消耗递归栈的空间，而大多数情况下都会通过使用系统递归栈来完成递归求解。对系统栈的频繁存取会影响到排序的效率。在数据量较大时，快速排序的复杂度为O(nlgn)。当数据集较小时，快排的复杂度有向O(n2)发展的趋势，此时不必继续递归调用快速排序算法，使用插入排序代替快速排序。STL中sort就是用的快排+插入排序的，使得最坏情况下的时间复杂度也是O(nlgn)这一改进被证明比持续使用快速排序算法要有效的多。使用一个快速排序的迭代模型可以使原递归算法所需的栈空间总量减至O（logn）。试设计这一迭代模型（算法）。struct nodeint low,high;st10000;void quicksort2(int data,int s,int t)int top=-1,low,high;top+;sttop.low=s;sttop.high=t;while(top-1)low=sttop.low;high=sttop.high;top-;int w;if(loww(v),则将v从T删除之后，T变为两个连同的分支，此时，一定有T的边v1连同这两个分支，否则T将是不连通的。从而将v1加入到T中构成一新的生成树T=T-v+v1。且有w(v1)w(v)w(v),从而w(T”)=w(T-v+v1)w(T)。这与T为最小生成树矛盾。证毕。据此利用prim算法或者Kruskal算法算得G的最小生成树即可Prim算法 O(n2)首先置 S=1，然后，只要S是V的真子集，就作如下的贪心选择：选取满足条件iS，jV-S，且cij最小的边，将顶点j添加到S中。这个过程一直进行到S=V时为止。在这个过程中选取到的所有边恰好构成G的一棵最小生成树。在上述Prim算法中，还应当考虑如何有效地找出满足条件iS, jV-S，且权cij最小的边(i,j)。实现这个目的的较简单的办法是设置2个数组closest和lowcost。在Prim算法执行过程中，先找出V-S中使lowcost值最小的顶点j，然后根据数组closest选取边(j,closestj)，最后将j添加到S中，并对closest和lowcost作必要的修改。Kruskal算法 O(eloge)首先将G的n个顶点看成n个孤立的连通分支。将所有的边按权从小到大排序。然后从第一条边开始，依边权递增的顺序查看每一条边，并按下述方法连接2个不同的连通分支：当查看到第k条边(v,w)时，如果端点v和w分别是当前2个不同的连通分支T1和T2中的顶点时，就用边(v,w)将T1和T2连接成一个连通分支，然后继续查看第k+1条边；如果端点v和w在当前的同一个连通分支中，就直接再查看第k+1条边。这个过程一直进行到只剩下一个连通分支时为止。6. 试设计在O(n)时间内求得数组A1.n的中位数的算法。将n个输入元素划分成n/5(上取整)个组，每组5个元素，只可能有一个组不是5个元素。用任意一种排序算法，将每组中的元素排好序，并取出每组的中位数，共n/5(上取整) 个。找出这n/5(上取整)个元素的中位数。如果n/5(上取整)是偶数，就找它的2个中位数中较大的一个。7. 两个数组找第k小元素事件复杂度O(log(k) )在网上看的，和同学商讨过，可行，认为此方法比上个log（m）+log（n）的方法要好 第一个数组m个元素 第二个数组n个元素分别从两个数组找第k/2个数，ak/2,bk/2;假设ak/2bk/2; 则ak/2 之前的以及ak/2都可以删去，并且k=k - 删去的元素下面分析为什么可以删去：因为ak/2bk/2,所以ak/2前至少有k/2-1个元素，至多有k/2-1 + k/2-1 =k-2 个元素，因为ak/2 and bk/2 之后的都不可能在ak/2 之前，所以ak/2排在最后时也排在第k-1个位置，都小于第k个元素，所以可删去。其他情况同理；当m或n小于k/2时，假设mX3，则A先猜出，否则就是C先猜出），这样就又安装上面的思路求解。这显然就是一个递归求解的过程。设函数Times(i,j,t1,t2,t3)表示编号为t1的人头上的数为i，编号为t2的人的数为j，编号为t3的人的数为i+j（即由t3最先猜出自己的数）时，教授需要提问的次数；P（t1,t2）表示教授按照1-2-3的顺序，从t1问到t2，最少需要提问的次数，则根据上面的分析，有如下关系： t3, i=jtimes(i,j,t1,t2,t3)=jtimes(i,j-i,t1,t3,t2)+P(t2,t3), it1时，P(t1,t2)=t2-t1,否则，P(t1,t2)=t2+3-t1寻找丢失的数！类C语言：用一个二维数组保存数组中的数的二进制位，然后从右往左按列扫描，然后确定之后删除被排除的行和，然后扫描第二次。特殊的整理：桶排序：桶排序工作的原理是：将阵列分到有限数量的桶子里。每个桶子再个别排序。当要被排序的阵列内的数值是均匀分配的时候，桶排序使用线性时间（n）。要对大小为1.1000范围内的n个整数A1.n排序，可以把桶设为大小为10的范围，具体而言，设集合B1存储1.10的整数，集合B2存储(10.20的整数，集合Bi存储(i-1)*10, i*10的整数，i = 1,2,.100。总共有100个桶。然后对A1.n从头到尾扫描一遍，把每个Ai放入对应的桶Bj中。 然后再对这100个桶中每个桶里的数字排序，这时可用冒泡，选择，乃至快排，一般来说任何排序法都可以。最后依次输出每个桶里面的数字，且每个桶中的数字从小到大输出，这样就得到所有数字排好序的一个序列了。 假设有n个数字，有m个桶，如果数字是平均分布的，则每个桶里面平均有n/m个数字。如果对每个桶中的数字采用快速排序，那么整个算法的复杂度是O(n+m*n/m*log(n/m)=O(n+nlogn-nlogm) 从上式看出，当m接近n的时候，桶排序复杂度接近O(n)。简答题：贪心和动态规划的区别！主要理解贪心的思想 局部！所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。 对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。贪心算法和动态规划算法都要求问题具有最优子结构性质，这是2类算法的一个共同点。雏形整理第一章和第二章：算法特性：有穷，可行，确定，输入，输出 四元组（Q，I，f）时间复杂性的定义掌握，理解上界，下界和精确界的证明过程，已经背下来了，分为多项式时间算法和指数时间算法； O(1) O(log n) O(n) O(n log n ) O(n2) O(2n) O(n!) O(nn) 买鸡问题：void chicken_problem(int n,int &k,int g,int m,int s)int i,j,a,b,c; k=0; i=n/5; j=n/3;for(a=0;a=i;a+)for(b=0;b=j;b+)c=n-a-b;if(5*a+3*b+c/3=n)&(c%3=0)gk=a;mk=b;sk=c;k+货郎担问题：void salesman_problem(int n,float &min,int t,float c)int pn,i=1;float cost;min=MAx_FLoat_NUM;while(i=n!)产生n个城市的第i个排列于p;cost=路线p的费用；if(costnext) if (L-next-data=x) p=L-next; L-next=p-next;delete(p); delete_L(L, x);else delete_L(L-next, x); / delete 汉诺塔：void hanoi(int n,char x,char y,char z)/将塔座x上按直径有小到大且至上而下编号为1-n的n个圆盘按规则搬到塔座z上，y可用作辅助塔座。if (n=1)move(x,1,z);/将编号为1的圆盘从x移到zelsehanoi（n-1,x,z,y）;/将编号为1至n-1的圆盘移动到y，z作辅助塔Move(x,n,z);/将编号为n的圆盘从x移到zHanoi（n-1,y,x,z）;/将y上编号为1至n-1的圆盘移到z，x作辅助（1） 合并排序： 合并排序时间复杂度的计算： 第k小元素 快速排序：主要思想：template void QuickSort (Type a, int p, int r)if (pr) int q=Partition(a,p,r); QuickSort (a,p,q-1); /对左半段排序 QuickSort (a,q+1,r); /对右半段排序最坏时间复杂度 O（n2）平均时间复杂度O（nlogn）辅助空间：O(n)或O（logn） 时间复杂度分析：快速排序的运行时间与划分是否对称有关，其最坏情况发生在划分过程产生的两个区域分别包含n-1个元素和n个元素。由于算法Partition(a,p,r)的计算时间为O（n）,所以如果Partition(a,p,r)的每一步都出现这种部队成划分，则其计算时间复杂性T(n)满足：解得在最好的情况下，每次划分所取得基准都恰好为中值，即每次划分都产生两个大小为n/2的区域，此时有：解得：快排在平均情况下的时间复杂性也是这个值。通过修改算法，可以设计出采用随机选择策略的快速排序算法。在快排的每一步中，当数组还没有被划分时，可以在ap:r中随机选择一个元素作为划分基准，这样可以使划分基准的选择是随机的，从而可以期望划分是比较对称的templateint RandomizedPartition (Type a, int p, int r) int i = Random(p,r); Swap(ai, ap);return Partition (a, p, r);1、 0-1背包问题 设所给0-1背包问题的子问题从m(i,j)的递归式容易看出，算法需要O（nc）计算时间。当背包容量c很大时，算法需要的时间较多。例如，当c2n时，算法需要欧米伽（n2n）计算时间。的最优值为m（i,j）,即m(i,j)是背包容量为j，可选物品为i，i+1，,n时0-1背包问题的最优值。由0-1背包问题的最优子结构性质，可以建立计算m(i,j)的递归式如下背包问题：首先计算每种物品单位重量的价值Vi/Wi，然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未超过C，则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去，直到背包装满为止。最优装载问题照着这个代码完全可以写出来！动态规划经典问题：证明0-1背包问题具有最优子结构性质如果（x1,x2,.,xn）是所给0-1背包问题的最优解，则(x1,x2,.,xn-1)是下列子问题的最优解。利用反证法证明。证明：假设(x1,x2,.,xn-1)不是最优解，而(y1,y2,.,yn-1)是最优解。由此可知:因此:上述结果说明： (y1,y2,.,yn-1,xn)是所给0-1背包问题的更优解。与前提矛盾。矩阵连乘问题：时间复杂度：O(n3)，空间复杂度; O(n2)平方最长公共子序列：分治与递归1、 两路归并排序【2-waysort MergeSort】 T(n)=nlogn-n+1=O(nlogn) 最坏时间复杂度，平均时间复杂度。2、 找最大元 T(n)=n-13、 大整数的乘法 把大整数分成两段，减少乘法次数，T(n)=O(n(log3)=O(n1.59)3 T(n/2) + k n ( n 1 )递归T(n) = k ( n = 1) k是整数4、 矩阵 1）普通算法 T(n)=O(n3) 2）Strassen算法 T(n)=O(nlog7)=O(n2.81)5、Hanoi塔算法 T(n)=O(2n) void hanoi(n,x,y,z) x源；z目的；y辅助；n盘子个数6、二分搜索（已排好顺序） T(n)=O(logn)7、棋盘覆盖chessBoard 2k*2k的棋盘，用到的L形骨牌个数恰为(4 k-1)/3。T(k)=O(4k)8、快速排序QuikSort(a,p,r) p上界，r下界。最坏时间复杂度O(n2);平均时间复杂度O(nlogn);9、最接近点对问题 T(n)=O(nlogn)贪心算法1、 活动安排问题1）活动已按结束时间的非递减顺序排列 O(n); 2）没排序 O(nlogn)2、 贪心算法的基本要素 两性质 1）贪心选择性2）最优子结构性质贪心选择性：所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是利用贪心算法求解最优解的第一个基本要素，也是贪心算法与动态规划算法的主要区别。 最优子结构性质：当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。 背包问题：贪心算法；0-1背包问题：动态规划（0-1背包问题不具有贪心选择性质。原因是无法保证能够将背包装满，而所剩空间将会降低总价值。）3、 最优装载 T(n)=O(nlogn)4、 哈夫曼编码O(nlogn)5、 单源最短路径O(n2)6、用贪心算法解背包问题的基本步骤： 1.计算每种物品单位重量的价值 Vi/Wi； 3.依据贪心选择策略，按照单位价值从高到低的顺序，依次将尽可能多的物品装入背包中。直到背包装满为止。是否可以将物品装入背包的条件是：有空间 动态规划2、 矩阵连乘问题 时间上界O(n3) 占用空间O(n2)3、 设计动态规划算法的步骤 1）找出最优解的性质，并刻画其结构特征；2）递归地定义最优值；3）以自底向上的方式计算出最优值；4）根据计算最优值时得到的信息构造最优解4、 动态规划算法的基本要素 1）最优子结构；2）子问题重叠 3）备忘录法5、 最长公共子序列 T(n)=O(mn)+O(m+n)6、 多段图问题 向前递推0-1背包与背包问题都具有最优子结构 已知背包最大承载重量为C，共有n个物品，每个物品的重量分别为Wi(i=1,2,.,n)，价值为 Vi(i=1,2,.n)。证明：假设第k个物品是最优解中的一个物品，则从中拿出Wk对应的物品后所对应的解一定是其余n-1个物品，装入背包最大承载重量为C-Wk的最优解，否则与假设矛盾。 Dijkstra算法1、Dijkstra算法具有最优子结构性质证明算法中每步确定的disti是当前从源点到顶 点i的最短特殊路径长度。 证明： 采用数学归纳法。 当|S|=1时，显然成立。 假设在第k次贪心选择之前disti存放着从源点到顶点i的最短特殊路径长度。 需要证明（第k+1次贪心选择）： 根据贪心选择策略，将顶点u添加到S之后，disti仍然是当前从源点到顶点i的最短特殊路径长度。 假设根据贪心选择策略，第k+1选 择将顶点u添加到S中，对于顶点i 可能会增加一条从源点到达顶点i 的新的特殊路径。 这条新的特殊路径由两种可能： 情况1： 这条路径先由源点到达顶点u，再由顶点u直接到达i， 则这条特殊路径的长度为： distu+aui 如果这条路径更短，替换disti；否则不变。 情况2： 如果新增加的特殊路径先由源点到达顶 点u，再由顶点u途径另一顶点x到达i。 由于x早于u进入S中，所以 distxdistu, 即distx+axidistu+aux+axi， 故：这条新特殊路径不会影响disti，因此不需 要考虑。 结论：在任何时候，disti都存放着当前从源点 到i点的最短特殊路径长度。 2、Dijkstra算法具有贪心选择性质 按照贪心选择方式得到的distu一定是从源点s到顶点u的最短路径长。 证明：假设存在一条从源点s到u的更短路径 d(s,x) 是从s 到x的路径长度，d(s,u) 是从s 到u的路径长度，d(x,u) 是从x 到u的路径长度 则distx d(s,x)， d(s,x)+d(x,u)=d(s,u)distu 由于d(x,u) 0， 所以distx0时，将2k2k棋盘分割为4个2k-12k-1 子棋盘。特殊方格必位于4个较小子棋盘之一中，其余3个 子棋盘中无特殊方格。为了将这3个无特殊方格的子棋盘转化为特殊棋盘，可以用一个L型骨牌覆盖这3个较小棋 盘的会合处，从而将原问题转化为4个较小 规模的棋盘覆盖问题。递归地使用这种分割，直至棋盘 简化为棋盘,即k=0,11。 棋盘覆盖分治算法伪语言 void chessBoard(int tr, int tc,int dr, int dc,int size) if(size=0)return ; / 覆盖左上角子棋盘 / 覆盖左下角子棋盘if ( 特殊方块在左上角) if ( 特殊方块在左下角)覆盖左上角;覆盖左下角;else else 在右下角放一小方块; 在右上角放一小方块;覆盖左上角; 覆盖左下角;/ 覆盖右上角子棋盘 / 覆盖右下角子棋盘if ( 特殊方块在右上角) if ( 特殊方块在右下角)覆盖右上角; 覆盖右下角;else else 在左下角放一小方块; 在左上角放一小方块;覆盖右上角; 覆盖右下角; 计算最优解的动态规划算法假设Ai的维数为pi-1pi，则输入序列为 p0, p1, p2, . ,pn pn+1 记录每个矩阵的维数;mi,j记录AiAi+1.Aj相乘的代价（乘法次数）;si,j记录取得最优代价所断开的点k具有自底向上的计算特征： 如果计算mi,j，仅需要计