由此可知: 因此:
上述结果说明： (y1,y2,...,yn-1,xn)是所给0-1背包问题的更优解。与前提矛盾。
32
矩阵连乘问题：时间复杂度：O(n)，空间复杂度;O(n)平方最长公共子序列：
分治与递归
1、 两路归并排序【2-waysort MergeSort】 T(n)=nlogn-n+1=O(nlogn) 最坏时间复杂度，平均时间复杂度。 2、 找最大元 T(n)=n-1
3、 大整数的乘法 把大整数分成两段，减少乘法次数，T(n)=O(n^(log3))=O(n^1.59)
3 T(n/2) + k n ( n > 1 )
递归T(n) = k ( n = 1) k是整数
4、 矩阵 1）普通算法 T(n)=O(n^3)
2）Strassen算法 T(n)=O(n^log7)=O(n^2.81)
5、Hanoi塔算法 T(n)=O(2^n) void hanoi(n,x,y,z) x源；z目的；y辅助；n盘子个数 6、二分搜索（已排好顺序） T(n)=O(logn)
7、棋盘覆盖chessBoard 2^k*2^k的棋盘，用到的L形骨牌个数恰为(4^ k-1)/3。T(k)=O(4^k) 8、快速排序QuikSort(a[],p,r) p上界，r下界。最坏时间复杂度O(n^2);平均时间复杂度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(n^2)
6、用贪心算法解背包问题的基本步骤：
1.计算每种物品单位重量的价值 Vi/Wi； 3.依据贪心选择策略，按照单位价值从高到低的顺序，依次将尽可能多的物品装入背包中。直到背包装满为止。是否可以将物品装入背包的条件是：有空间 动态规划
2、 矩阵连乘问题 时间上界O(n^3) 占用空间O(n^2)
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算法具有最优子结构性质
证明算法中每步确定的dist[i]是当前从源点到顶 点i的最短特殊路径长度。 证明： 采用数学归纳法。
当|S|=1时，显然成立。 假设在第k次贪心选择之前dist[i]存放着从源点到顶点i的最短特殊路径长度。
需要证明（第k+1次贪心选择）： 根据贪心选择策略，将顶点u添加到S之后，dist[i]仍然是当前从源点到顶点i的最短特殊路径长度。 假设根据贪心选择策略，第k+1选 择将顶点u添加到S中，对于顶点i 可能会增加一条从源点到达顶点i 的新的特殊路径。
这条新的特殊路径由两种可能： 情况1：
这条路径先由源点到达顶点u，再由顶点u直接到达i， 则这条特殊路径的长度为： dist[u]+a[u][i] 如果这条路径更短，替换dist[i]；否则不变。 情况2：
如果新增加的特殊路径先由源点到达顶 点u，再由顶点u途径另一顶点x到达i。 由于x早于u进入S中，所以 dist[x]≤dist[u], 即dist[x]+a[x][i]≤dist[u]+a[u][x]+a[x][i]， 故：这条新特殊路径不会影响dist[i]，因此不需 要考虑。
结论：在任何时候，dist[i]都存放着当前从源点 到i点的最短特殊路径长度。 2、Dijkstra算法具有贪心选择性质
按照贪心选择方式得到的dist[u]一定是从源点s到顶点u的最短路径长。 证明：假设存在一条从源点s到u的更短路径
d(s,x) 是从s 到x的路径长度，d(s,u) 是从s 到u的路径长度，d(x,u) 是从x 到u的路径长度 则dist[x] ≤d(s,x)， d(s,x)+d(x,u)=d(s,u) 由于d(x,u) ≥0， 所以dist[x] 算法：是满足下述性质的指令序列。 有限性：每条指令的执行次数、时间有限 确定性：每条指令有确定的含义、无歧义 输入：0个或多个输入 输出：1个或多个输出 程序：是算法用某种程序设计语言的具 体实现。程序可以不满足算法的有限性。 设计算法的基本过程 分析问题域，确定数学模型 首先整理初始状态与结果状态之间的隐含关系，然后寻求从数学模型已知初始状态到达结果状态的运算步骤，即算法 算法复杂性是算法运行所需要的计算机资源量，需要的时间资源量称为时间复杂性，需要的空间资源量称为空间 复杂性。这些量只依赖于算法所要求解问题的规模、算法的输入和算法本身。 O的定义：如果存在正常数c和自然数n0，使得当n≥n0时，有f(n) ≤cg(n)， 则称函数f(n)当n充分大时有上界，且g(n)是它的一个上界， 记f(n)= O(g(n))。 即f(n)的阶不高于g(n)的阶。 Ω的定义：如果存在正的常数c和自然数n0 ， 使得当n ≥ n0时有f(n) ≥ cg(n)，则称函数 f(n)当n充分大时有下界，且g(n)是它的一个 下界，记为f(n)=Ω(g(n))。 即f(n)的阶不低于g(n)的阶。 f(n) = Ω(g(n)) θ的定义： 如果存在三个正常数c1,c2和n0，使得 当n ≥ n0时， c1g(n) ≤f(n) ≤c2g(n) 则记f(n)= θ(g(n))。 即f(n)与g(n) 同阶 回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时， 先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索 回溯法的求解过程 由于问题的解向量X=(x1, x2, ?, xn)中的每个分量xi(1≤i≤n) 都属于一个有限集合Si={ai1, ai2, ?, airi}，因此，回溯法可以按某种顺序（例如字典序）依次考察笛卡儿积S1×S2×?×Sn中的元素。 初始时，令解向量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, ?, xi＋1)是问题的最终解，则输出这 个解。如果问题只希望得到一个解，则结束搜索，否则继续搜索其他解； 2、如果X=(x1, x2, ?, xi＋1)是问题的部分解，则继续构造解向量的下一个分量； 3、如果X=(x1, x2, ?, xi＋1)既不是问题的部分解也 是问题的最终解，则存在下面两种情况： （1）如果xi+1= ai＋1k不是集合Si＋1的最后一个元 素， 则令xi+1= ai＋1k＋1，即选择Si+1的下一个元素作为解向量X的第i+1个分量； （2）如果xi+1= ai＋1k是集合Si＋1的最后一个元素，就回溯到X=(x1,x2, ?, xi)，选择Si的下一个元素作为解向量X的第i个分量，假设xi= aik，如果aik不是集合Si的最后一个元素，则令xi= aik＋1；否则，就继续回溯到X=(x1, x2, ?, xi－1)； 棋盘覆盖 放置一个三格板后，棋盘中间区域已经放置好。如果把这个三格板看成三个残缺格，原来的残缺棋盘就可以分成4个残缺棋盘。虽然这个三个棋盘与原来棋盘不相似，但是通过放置一个三格板，可以将原来不相似的三个棋盘构造成残缺棋盘，这样这三个棋盘的放置方法可以采用类似原来残缺棋盘的放置方法。 当残缺棋盘的规模降为2*2时，这时棋盘不再分解，递归终 止，因为这时残缺棋盘只要放置一个三格板就可以铺满。 当k>0时，将2k×2k棋盘分割为4个2k-1×2k-1 子棋盘。特殊方格必位于4个较小子棋盘之一中，其余3个 子棋盘中无特殊方格。为了将这3个无特殊方格的子棋盘转化为特殊棋盘，可以用一个L型骨牌覆盖这3个较小棋 盘的会合处，从而将原问题转化为4个较小 规模的棋盘覆盖问题。递归地使用这种分割，直至棋盘 简化为棋盘,即k=0,1×1。 棋盘覆盖分治算法伪语言 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-1×pi，则输入序列为{ p0, p1, p2, ... ,pn } p[n+1] 记录每个矩阵的维数; m[i,j]记录AiAi+1...Aj相乘的代价（乘法次数）; s[i,j]记录取得最优代价所断开的点k 具有自底向上的计算特征： 如果计算m[i,j]，仅需要计算小于j-i+1个的矩阵乘积。 即计算长度为L的矩阵相乘代价仅依赖于小于L长度的矩阵相乘代价。 算法思路： 按照长度递增(1,2, ... n) 计算m[i,j]代价。 算法matrixChain，首先计算出m[i,i]=0,i=1,2,?,n。然后，根据递归式，按矩阵链长递增的方式依次计算： m[i,i+1],i=1,2,?,n-1,(矩阵链长度为2）； m[i,i+2],i=1,2,?,n-2, (矩阵链长度为3）?； 在计算m[i,j]时，只用到已计算的m[i,k]和m[k+1,j]; 动态规划算法的基本要素 （1）最优子结构 矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。 （2）重叠子结构 在利用递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。这种性质称为子问题的重叠性质 分支限界法的基本思想 分支限界法采用广度优先或最小耗费（最大效益）优先的方式搜索问题的解空间树。 在分支限界法中，每一个活结点只有一次成为扩展结点的机会。活结点一旦成为扩展结点，就一次性产生所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被剪掉，其余儿子结点被加入活结点表中。 此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到满足约束条件的解或活结点表为空时为止。 分支限界法与回溯法的不同 （1）求解策略：回溯法的求解过程属于盲目搜 索，而分支限界法的求解过程是有选择地朝有利于获得问题解或最
