以背包问题为例课件.ppt

1、目录10.1算法分析技术算法分析技术 10.1.1 空间代价分析空间代价分析 10.1.2 时间代价分析时间代价分析10.2算法设计技术算法设计技术 10.2.1 分治法分治法 10.2.2 贪心法贪心法 10.2.3 动态规划法动态规划法 10.2.4 回溯法回溯法 10.2.5 分枝界限法与分枝界限法与0/1背包问题背包问题*10.1 算法分析技术评价一个算法的代价，主要看执行算法时所需要占用的计算机空间的大小和计算过程需要花费的计算机CPU时间的多少。算法的分析主要包含时间和空间两个方面。10.1.1 空间代价分析根据算法执行过程中对存储空间的使用方式，可以把对算法空间代价分析分成两种：

2、静态分析和动态分析。一个算法静态使用的存储空间，称为静态空间。静态分析的方法比较容易，只要求出算法中使用的所有变量的空间，再折合成多少空间存储单位即可。静态分析例例10.1直接插入排序的空间代价分析（参看算法8.1）被排序的记录的个数决定了问题的规模。被排序的对象在调用函数中申请，并用一个指针变量pvector传递给被调函数，空间大小显然是O(n)；在排序程序中，算法以静态方式定义了两个整型变量i和j、一个存储插入元素的临时变量temp，所以在算法中分配的空间为一个 常量，记为O(1)（对于常量c而言，O(c)与O(1)为相同复杂度）。动态分析动态分析一个算法在执行过程中，必须以动态方一个算法

3、在执行过程中，必须以动态方式分配的存储空间是指在算法执行过程式分配的存储空间是指在算法执行过程中才能分配的空间称为动态空间。中才能分配的空间称为动态空间。动态空间的确定主要由两种情况构成：（1）函数的递归；（2）执行动态分配函数。对于递归函数而言，由于每次调用需要分配不同的运行空间，所以递归函数的空间代价，不能简单地采用静态分析方法。假设静态分析一个递归函数的空间代价为一个常量c，如果递归深度为（h的大小依赖于程序的动态执行），动态空间代价应该为C*h。函数的递归调用例例10.2 快速排序（参看算法8.8）对函数静态分析的空间与待排序记录的个数无关，为一常量。递归深度最大等于，这时动态空间代价

4、为O(n)；若每次都选较短的部分先处理，则递归深度不会超过log2n，这时动态空间代价即为O(log2n)。一个函数（或过程）如果使用了malloc和free函数，malloc和free所开辟、释放的空间只能在算法执行过程中加以确定，这些空间属于动态空间。下面的讨论中，假设每次分配的空间与问题规模无关，只是一个常数C。执行动态分配函数没有使用free函数 动态空间代价为O(k)，k为使用malloc的次数（包括在循环和递归调用中动态执行的次数）。分如下两种情况讨论：使用使用free函数函数 设free使用次数为j。令：0，pi（i=1.j）为第i-1次使用free和次使用free之间 执行ma

5、lloc的次数。用公式i=i-1+p i-1 可以计算出在第i-1次使用free和第i次使用free（i=1.j）之间使用的最大动态空间数。再定义j如下：于是整个算法使用的动态空间代价为：使用。无后次使用若第使用；有后次使用若第malloc,freej,jmalloc,freej,1jj)Cmax(Oiji1例例10.3 一个算法执行过程中malloc和free顺序为（代表malloc，代表free）。,jj0=，1，2，3，4，5，6，7。3max71iiC10.1.2 时间代价分析时间代价分析 算法的执行时间绝大部分花在循环和递归上。循环循环语句的时间代价一般用以下三条原则分析：（）对于一

6、个循环，循环次数乘以每次执行简单语句的数目即为其时间代价。（）对于多个并列循环，可先计算每个循环的时间代价，然后按大表示法的加法规则计算总代价。（）对于多层嵌套循环，一般可按大表示法的乘法规则计算。但如果嵌套是有条件的，为精确计算其时间代价，要仔细累加循环中简单语句的实际执行数目，以确定其时间代价。例例10.510.5求带权图中每一对结点之间的最短路径的算法的时间代价（参看算法9.7）。解 问题规模：带权图顶点数目为。算法中共有五个循环，前两个循环与后三个是并列关系。前两个循环是嵌套关系，后三个之间也是嵌套关系。最内层循环的时间代价为一常数C，则前两个循环时间代价为：后三个循环时间代价为：所以

7、总的时间代价为O(n3)。ninjnOC112;)(ninjnknOC1113)(。例例10.6 为实现无回溯的匹配，而要计算模式串的NEXT数组算法的时间代价（参看算法3.8）。问题规模：模式串长度。从形式上来看，这是一个二重循环，每重循环最多执行m次，最大运行时间可能达到O(m2)。仔细分析：因为每执行一次外层（第4行）循环，i严格增1（第6行），所以外层循环正好执行m1次；但是，k的值从（第2行）-1开始，k+恰好执行（第6行）m1次，并且只有在这一语句中k被增值。而在内层循环（第5行）中，语句knextk至少使k减少1，整个算法中，这个语句的执行次数累计起来不可能超过m1次（否则，k将

8、小于-1，这是不可能的），所以内层循环总的执行次数最大为m1。因此算法3.8的执行时间为O(m)。递归对于递归算法，一般可把时间代价表示为一个递归方程。解这种递归方程最常用的方法是进行递归扩展，通过层层递归，直到递归出口，然后再进行化简。例如例如，有某递归算法，当n=1时是递归出口，执行的时间是一个常量；当n1时，可以把问题分解成a（a=1）个子问题的递归计算，每个子问题的规模是原来问题的b(b=1)分之一；分解问题和合并子问题解的花费为d(n)。整个问题的时间代价可以表示为下面一类递归方程的计算：。为正常数)b(a,(n)dT(n/b)aT(n)1;T(1)递归扩展过程如下：10223322

9、2222)/()/()()/()/()/()()/()/()/()()/()/()()/()/()()/()(ijjjiibndabnTandbnadbndabnTandbnadbndbnaTandbnadbnTandbndbnaTandbnaTnT设k，则又设d(x)为“积性函数”：d(x*y)=d(x)*d(y)1k0jjkjkk)b(daa)n(T,1)1(T)b/n(T则有：1)()(1)(1)()()()()()()(101010bdabdabdabdabdbdabdabdbdabdakkkkkjjkkjjkjkjjkj时当以下分三种情况讨论：（1）d(b)，则 kkkaO1)b(d

10、a)b(d(a)n(O)n(O)a(O)a(O)a(O)a(O)a(O)a(O)n(Talogblog1blog1nlogblognlognlogkkkbaaaaab（2）d(b)，则),)b(d(O1)b(da)b(d(akkk)n(O)b(d(O)b(d(O)a(O)n(T)b(dlogkkkb（3）d(b)，则,kaa)b(d(ak1k0j1k0jkjkj)nn(logO)ka(O)ka(O)a(O)n(Talogbkkkb例例10.810.8求快速排序法的时间代价。此算法的递归方程可表示为：T(n)T(n/2)n，这里，d(x)是积性函数。因为d(b)，所以 结论与8.4节所得结果一样

11、。)log()(log)(22log22nnOnnOnT10.2 10.2 算法设计技术算法设计技术 10.2.1分治法分治法分治法(Divide and Conquer)是把一个规模为的问题分成两个或多个较小的与原问题类型相同的子问题，通过对子问题的求解，并把子问题的解合并起来从而构造出整个问题的解，即对问题分而治之。如果子问题的规模仍然相当大，可以对此子问题重复地应用分治策略。分治法的算法框架return_type d_and_c(objArray*p,int i,int j)int temp;if(simple(p,i,j)return solve(p,i,j);/*基值处理*/temp

12、=divide(p,i,j);/*分解问题*/return(combine(d_and_c(p,i,temp-1),d_and_c(p,temp,j);/*递归调用与合并处理*/例子二分法检索就是我们所学过的应用分治策略的典型的例子。快速排序算法，归并排序算法、梵塔问题等都可以用分治策略求解。快速排序算法每趟把一个元素放入排完序后它所应在的位置，这个位置把原表分成了两个宏观有序的子表；归并排序算法是把规模为的问题分成规模为n/2的两个子问题；而梵塔问题分原问题为两个规模为n-1的子问题。讨论分治策略把问题分成若干个子问题，分成的子问题的数目一般不大。如果每次分成的各子问题的规模相等或近乎相等的

13、话，则分治策略的效率较高，否则效率就比较低。例如：直接插入排序（算法8.1）可以看作是把原问题分解成两个子问题，一个是规模为的问题，另一个是规模为n-1的问题，算法的时间代价是O(n)级的。而归并排序把原问题分成了两个大小为n/2的问题，算法的时间代价是O(nlog2n)级的。10.2.2贪心法贪心法求着色问题近似解的贪心法贪心法(greedy)其基本思想为：先用一种颜色给尽可能多的结点上色，然后再用另一种颜色在未着色的结点中给尽可能多的结点上色，如此反复直到所有结点都被着色为止。Dijkstra的最短路径算法 求从源点到其它各结点的最短路径 它总是从那些最短路径还不知道的结点中挑选一个到源点

14、最近的结点。另一采用贪心策略的算法是Kruskal的求最小生成树算法背包问题：给定个物体和一个背包，已知物体的重量为i，价值为pi，背包能容纳物体的重量为。要求确定一组分数i（i），能够把物体的i部分放入背包，使得 最大（即将尽量多的价值装入背包）。n1iiixp因为：p/w25/181.38，p/w24/151.6，p3/w315/101.5，p/wp/wp/w。所以首先把物品2全部放入背包，然后考虑物品3，最后如果还有余地考虑物品1。这样得到的结果为（x，x2，x3）（0，1，1/2），例如：3，20，(p1,p2,p3)=(25,24,15),(w1,w2,w3)=(18,15,10)解

15、背包问题的贪心算法的实现：其中参数数组其中参数数组p和和w中中,按按pi/wi的降序分别存放物体的价格和重量；的降序分别存放物体的价格和重量；m是背包是背包能放的物体总重量，能放的物体总重量，n是物体件数。是物体件数。x存放解向量。存放解向量。float knapSack(float*p,float*w,float*x,float m,int n)int i=0;float s=0;while(in&pim)m-=wi;s+=pi;xi=1;i+;if(i0)s+=pi*m/wi;xi=m/wi;i+;for(;in;i+)xi=0;return(s);讨论贪心法在各个阶段，选择那些在某些意义

16、下是局部最优的方案，但不是每次都能成功地产生出一个整体最优解。仍然以着色问题为例，如果要着色的图如图10.1所示，采用贪心法，并且按a、b、c、d、e的顺序处理，得到的结果则需要三种不同的颜色：第一种颜色着a和b，第二种颜色着c和d，剩下的e还需要一种颜色才行。对某些问题，如果只要求得一个与最优解相差不多的次优解就满足要求时，选用贪心法可以帮助我们很快地得到这样的解。a e c d b 10.2.3 动态规划法动态规划法有些问题常常在分解时会产生大量的子问题，同时子问题界限不清，互相交叉，因而可能重复多次解同一个子问题。解决这种重复的方法：可以在得到每个子问题的解（包括其子子问题的解）时，把解

17、保留在一个表格中，遇到相同的子问题时，就从表中找出来直接使用。这种方法就是动态规划法动态规划法（Dynamic Programming）。例例10.1010.10求组合数。我们知道组合数有这样的一个递推式：每次求解可将其分为两个子问题和。把 按递推式分解得到图10.2的二叉树结构。或nm0n,1C;0nm,CCCnm1n1mn1mnm35C例子本书所见过的运用动态规划法的算法有：所有结点间的最短路径算法最佳二叉排序树的构造算法。例例10.10求组合数组合数有下面的递推式：。或nm0n,1C;0nm,CCCnm1n1mn1mnm把35C按递推式分解 得到的二叉树结构。首先，将的位置上以及0的位置

18、上元素皆填为1。填某一中间表目时，只要把它右边表目的元素与右下方表目的元素之和填入即可。这样，很快就能求出 10。35C计算计算组合数组合数的动态规划算法的动态规划算法：int combinat(int m,int n)int i,j;int mat10001000;if(n=0|m=n)return 1;for(j=0;jn;j+)mat0j=1;for(i=1;i=m-n;i+)if(j=0)matij=i+1;elsematij=mati-1j+matij-1;/*计算Cmn */return(matm-nn-1);/*返回计算的结果*/问题的规模越大，用动态规划法的好处就越明显地体现出

19、来。填完整个表，得到题目所求，花的时间要大大快于不填表递归的求解所花的时间。设题目的规模为，分治法时间代价是O(2n)，而动态规划法的时间代价仅要O(n2)。因此，在解这类问题时，一般采用动态规划法。动态规划法的好处动态规划法的好处区别区别1动态规划法先求子问题的解，然后通过求解子问题构造原问题的解；而贪心算法是直接地解原问题。区别区别2动态规划法通过对若干局部最优解的比较，去掉了次优解，从而产生了更高一层次的局部最优解。相当于对较低层次的局部最优解进行贪心的选择而得到高一级的局部最优解，因而最终产生一个最高层次的局部最优解。而贪心法每阶段只作一个挑选，各阶段的解一经选出就固定不变了，后阶段的

20、局部最优是基于前阶段的挑选，所以往往只能求出次优解。动态规划法与贪心法的区别动态规划法与贪心法的区别动态规划法与分治法的比较共同点共同点是:把一个大问题分解为若干较小的子问题，通过求解子问题而得到原问题的解。不同点不同点是：分治法每次分解的子问题数目比较少，子问题之间界限清楚，处理的过程通常是自顶向下进行；动态规划法分解的子问题可能比较多，而且子问题相互包含，为了重用已经计算的结果，要把计算的中间结果全部保存起来，通常是自底向上进行。10.2.4 回溯法有一类问题，要求找到一个满足某些条件的最优解，如果进行彻底的搜索，要进行大量的比较，要以大量的运算时间为代价。回溯法回溯法（backtrack

21、ing）求助于回溯技巧，常常可以大大地减少实际的搜索数目。例子第4章中给出的求解迷宫问题的算法4.11，采用的就是典型的回溯方法，另外关于深度优先对树、二叉树和图的周游算法中也直接采用了回溯的思想。由于回溯方法的本质是用深度优先的方法在解的空间树中搜索。所以在算法中都需要建立一个栈，用来保存搜索的路径。一旦产生的部分解序列不合要求，就要从栈中找到回溯的前一个位置，继续试探。一般回溯方法的程序结构：void backtrack(void)准备初值；do while(范围未超界并且工作未完成)分析条件；/*保证满足条件才往下去*/if(成功)路径进栈；由第一选择开始进入下一层；/*纵向走*/els

22、e 本层更换选择；/*横向走*/if(工作未完成)弹出堆栈；原来的上一层更换为下一选择；/*回溯到上层横向*/while(全部工作未完成)；输出结果；给定图10.6，其中，标明七个区域，要求用不多于四种颜色对这七个区域进行着色，使得有公共界的区域不同色（就象世界地图上，相邻的国家着不同的颜色一样）。例例10.1210.12四色问题：回溯法回溯法：按区域编号从小到大顺序着色。按色数从小到大的顺序进行试探。如试探成功，则对下一区域着色；如不成功，则用本区域的色数加再试探；如果色数大于，则退回上一区域，改色（已着的颜色的色数加）再试探。需要注意的是：按照顺序进行试探，这是至关重要的，它保证了搜索的系

23、统性和彻底性。存储表示存储表示：为了用程序实现这个算法，可以先把所给的问题化为下列无向图的形式,图中每一个顶点对应一个区域，区域有公共边界表现为相应顶点间有边连接。再选择适当的数据结构（例如用相邻矩阵表示图）就可以实现这个算法。01 02 03 05 07 04 06 应用回溯方法解问题时，这问题的解须能表示为一个元组。回溯方法通过系统的搜索来确定出问题的解。四色问题的解含于（，）到（，）之间的七元组中(可以用树形结构来表示这些元组)。我们可以构造出一棵解空间树：它是一棵高度为7的四叉完全树，共有47个叶子。解问题就相当于用一种方法周游这棵树，从树根到树叶之间的路径就是一个元组（一个后选的解）

24、。解空间树解空间树穷举测试是对所有的叶子都一一测试，而回溯的方法是从树根开始，边试探边往下走，若在某一层次查明不符合题意，则不往下走，砍掉以下的树杈，跳到下一杈上继续试探着往下走。这样边走边砍，砍掉大量的树杈，从而省掉大量测试。一旦走到叶子，就找到了一组解。回溯与剪枝回溯与剪枝四色问题的搜索树10.2.5 分枝界限法与分枝界限法与0/10/1背包问题背包问题分枝界限法分枝界限法（branch and bound）也是一种在表示问题解空间的树上进行系统搜索的方法。所不同的是，回溯法使用了深度优先策略，而分枝界限法一般采用广度优先策略，同时还采用最大收益（或最小损耗）策略来控制搜索的分枝。假设给定

25、n个物体和一个背包，物体i的重量为wi，价值为pi（i=1,2,n），背包能容纳的物体重量为m，要从这n个物体中选出若干件放入背包，使得放入物体的总重量小于等于m，而总价值达到最大。0/10/1背包问题背包问题如果用xi=1表示将第i件物体放入背包，用xi=0表示未放入，则问题变为选择一组xi 使得 与例10.9的背包问题相比，这里的xi只能取0或1两种值，所以称为0/1背包问题背包问题。11nniiiiiiwxw xmpxp x，并且最大例例10.14 0/1背包一个具体的0/1背包实例：已知n=4,m=15,w=(2,4,6,9),p=(10,10,12,18)求解x=(x1,x2,x3,

26、x4)，（xi=0,1），使得11nniiiiiiwxw xmpxp x，并且最大在图10.10中把本题所有可能的解用一棵高度为4的完全二叉树表示出来。图中给每个结点的圆圈内加上一个数字作为结点的标记；结点的附近标有一个与当前位置对应的x值，形式为（x1,x2,x3,x4），其中xi=?表示xi的取值尚未确定；每个结点的附近还有一对用括起来的数字，其中第一个数字表示当前位置已放入背包的物体重量，后面的数字表示当前位置已放入物品的价值。0/1背包问题的解空间树 在符合条件的解中，结点29的wp=38是最大值，x的值为（1，1，0，1），是最优解。由于x的取值个数随物体个数n按2n速度增长，所以求

27、出所有的可行解再选取最优解的时间代价太大。为了提高求解的效率，我们很容易想到上一节介绍的回溯法，通过回溯可以删除不必要的分枝。但是，遗憾的是，对本例而言，只有叶结点23，27，31可以忽略，因此改进不大。回溯算法的另一个缺点是：在搜索过程中即使找到了最优解也不能马上确定它就是最优的，只有把它所有的可行解全都求出来以后才能确定最优解。这种方法对树中的每个结点定义了一对界，分别给出沿着该结点继续搜索可能得到的解的收益上界（用收益上界（用u表示）和收益表示）和收益下界（用下界（用l表示）表示）。这两个值给得越精确，剪枝的控制就越有效。分枝界限法在剪枝的技术方面分枝界限法在剪枝的技术方面增加了智能的成

28、分增加了智能的成分假如0/1背包问题的最优解已经求出，解的px值一定不能超过用一般的（算法10.2所求的背包问题的）最优解的价值。因此我们就可以用相同条件的由贪心法求出的背包问题解的价值，作为这里0/1背包最优解收益的上界。以背包问题为例，以背包问题为例，来说明如何求出每个结点的来说明如何求出每个结点的u值。值。0/1背包问题的收益的下界可以选用它自己的任何一个可行解的收益作初值。我们不妨把它就取成：由算法10.2求出的收益上界减去求解过程中最后放入背包的xi1的物品的相应部分价值。它显然一定是这个0/1背包问题的一个可行解。以背包问题为例，以背包问题为例，来说明如何求出每个结点的来说明如何求

29、出每个结点的l值。值。用以上方法求出背包问题的上/下界，作为图10.9中根结点的u(1)和l(1)值为：u(1)=38 (对应于算法10.2的解为x=(1,1,1,1/3)l(1)=32（对应于0/1背包问题的可行解为x=(1,1,1,0)）然后用同样的思想对图中每个结点都可以求出各自的u,l值。分枝界限法的关键在于：可以利用求出的分枝界限法的关键在于：可以利用求出的各个结点的收益上各个结点的收益上/下界，有效地实现剪枝。下界，有效地实现剪枝。例如，通过上面对结点2和3的计算结果，可以知道，沿结点2继续搜索最好的结果是得到32的收益，但是如果沿结点3继续的话，至少可以保证32的收益。因此如果我

30、们只希望找到一个最优解的话，就可以把以2为根的子树全部剪掉。注意，这一剪枝，把整个问题求解的空间砍去一半！根据以上的思路可以剪掉很多分支，达到加快搜索的目的。具体的剪枝和搜索过程请参见教材。在使用分枝界限法搜索解的空间时，从根结点出发，每个结点最多处理一次，在生成当前结点的子结点时，把所有符合题目要求（wxm）并且在已知界值之内的结点放在一个活结点表中，然后从活结点表中选取出一个结点作为当前结点。计算它的收益上/下界，然后根据计算结果到活结点表中检查可以剪去的分支。如此反复直到活结点表中只剩下一个叶结点为止。0/1背包问题的解法很多，除去本节介绍的穷举法、回溯法、最大收益（最小代价）分枝界限法

31、、FIFO分枝界限法等以外，也可以采用动态规划的方法。当0/1背包问题的n足够大时，如果只想得到一个较好的可行解，采用前面介绍的贪心法或者分治法有时也是十分有效的。小结小结算法的分析主要包含时间和空间两个方面，空间代价分析分成两种情形：静态分析和动态分析。静态空间分析中，值得注意的是数组（静态数组），动态空间的确定主要考虑两种情况：函数的递归调用和空间的动态分配/回收。算法的执行时间绝大部分花在循环和递归上，循环的时间代价一般可以用加法规则和乘法规则估算；对于递归算法，一般可以解递归方程计算。分治法通过把问题化为较小的问题来解决原问题，从而简化或减少了原问题的复杂度；贪心法通过分阶段地挑选最优

32、解，较快地得到整体的较好解，在问题要求不太严格的情况下，可以用这个较优解替代需要穷举所有情况才能得到的最优解；动态规划法用填表的方法保存了计算的中间结果，从而避免了大量重复的计算；回溯法跳过大量无须测试的元组，很快地得到需要的解。分枝界限法是在系统搜索问题解的空间时，加入上下界的条件检查以达到有效剪枝的目的。这些方法的共同之处是运用技巧避免穷举测试。分治法和动态规划法都是将问题分成子问题来做的；贪心法、动态规划法以及回溯法都是从某一集合中选出子集，通过一系列的判定来得到解；贪心法、分枝界限法和回溯法都要进行逐项的测试比较逐步达到整个解；而动态规划法和回溯法都是逐步逼近最优解而最终得到满足条件的解。分枝界限法、动态规划法和回溯法得到问题的最优解；贪心法既可能得到次优解，也可能得到最优解，依赖于具体问题的特点和贪心策略的选取。对于某一问题来说，能用不同的设计技巧得到不同的算法。一个算法中，也可以结合使用几种算法设计技巧。如快速排序算法是分治的技巧和回溯的技巧的结合，其中分治的技巧是主要的。