1、第一章第一章 算法概述算法概述第二章第二章 递归与分治策略递归与分治策略第三章第三章 动态规划动态规划第四章第四章 贪心算法贪心算法第五章第五章 回朔法回朔法第六章第六章 分支限界法分支限界法第七章第七章 随机化算法随机化算法算法设计与分析算法设计与分析 目录目录1ppt课件4.2 4.2 贪心算法基本要素贪心算法基本要素4.1 4.1 活动安排问题活动安排问题4.3 4.3 最优装载问题最优装载问题算法设计与分析算法设计与分析 目录目录4.7 4.7 多机调度问题多机调度问题2ppt课件算法设计与分析算法设计与分析 贪心算法贪心算法4.1 4.1 活动安排问题活动安排问题有有n n个活动个活
2、动E=1,2,E=1,2,n n,其中每个活动要使用同一其中每个活动要使用同一资源资源,同一时间只允许一个活动使用该资源同一时间只允许一个活动使用该资源.每个活动每个活动i i都有一个都有一个开始时间开始时间s si i,和一个和一个结束时间结束时间f fi i.如果选择活动如果选择活动i i,则它在时间区间则它在时间区间 s si i,f fi i )内占用该资内占用该资源源;若区间若区间 s si i,f fi i )与与 s sj j,f fj j )不相交不相交,则称活动则称活动i i与与j j是是相相容的容的(兼容的兼容的).活动安排问题是要求在所给的活动集合中选出最大活动安排问题是
3、要求在所给的活动集合中选出最大相容活动子集相容活动子集.3ppt课件u在安排时应该将在安排时应该将结束时间早的活动结束时间早的活动尽量往尽量往前安排，好给后面的活动安排留出更多的前安排，好给后面的活动安排留出更多的空间，从而达到安排最多活动的目标。空间，从而达到安排最多活动的目标。u贪心准则应当是：贪心准则应当是：在未安排的活动中挑选在未安排的活动中挑选结束时间最早的活动安排。结束时间最早的活动安排。算法设计与分析算法设计与分析 贪心算法贪心算法直观想法直观想法4ppt课件算法设计与分析算法设计与分析 贪心算法贪心算法算法思路算法思路1.将活动按将活动按结束时间排序结束时间排序,得到活动集得到
4、活动集E=e1,e2en；2.先将先将e1选入结果集合选入结果集合A中，即中，即A=e1；3.依次扫描每一个活动依次扫描每一个活动 ei:如果如果ei的的si 最后一最后一个选入个选入A的活动的活动ej的的 fj,则将则将ei选入选入A中中,否则否则放弃放弃ei。5ppt课件算法设计与分析算法设计与分析 贪心算法贪心算法定理：定理：考虑任意非空子问题考虑任意非空子问题Sk，令，令am是是Sk中结束时间中结束时间最早的活动，则最早的活动，则am在在Sk的某个最大兼容活动子集中。的某个最大兼容活动子集中。证明：证明：令令Ak是是Sk的一个最大兼容活动子集，且的一个最大兼容活动子集，且aj是是Ak中
5、结中结束时间最早的活动。束时间最早的活动。若若aj=am，则证明，则证明am在在Sk的某个最大兼容活动子集中。的某个最大兼容活动子集中。若若ajam，令集合，令集合 ,即将即将Ak中的中的aj替换替换am因为因为Ak中的活动都是不相交的，中的活动都是不相交的，aj是是Ak中结束时间最早的中结束时间最早的活动，而活动，而fmfj，所以，所以Ak中的活动都是不相交的。中的活动都是不相交的。由于由于|Ak|=|Ak|，因此得出结论，因此得出结论Ak也是也是Sk的一个最大活动的一个最大活动子集，且它包含子集，且它包含am。mjkkaaAA6ppt课件2.2.最优子结构性质最优子结构性质n当一个问题的最
6、优解包含其子问题的最优当一个问题的最优解包含其子问题的最优解时，称此问题具有解时，称此问题具有最优子结构性质最优子结构性质。n问题的最优子结构性质是该问题可用动态问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。规划算法或贪心算法求解的关键特征。算法设计与分析算法设计与分析 贪心算法贪心算法7ppt课件3.3.贪心算法与动态规划算法的差异贪心算法与动态规划算法的差异算法设计与分析算法设计与分析 贪心算法贪心算法 相同点：相同点：都具有最优子结构性质都具有最优子结构性质 区别：区别：动态规划法动态规划法贪心算法贪心算法选择特征选择特征往往依赖于相往往依赖于相关子问题的解。关子
7、问题的解。只有只有解出相关解出相关子问题才能作子问题才能作出选择出选择。当前状态下作当前状态下作出最好选择，出最好选择，即局部最优选即局部最优选择，但择，但不依赖不依赖于子问题的解于子问题的解设计特征设计特征自底向上自底向上自顶向下自顶向下8ppt课件算法设计与分析算法设计与分析 贪心算法贪心算法背包问题背包问题 给定给定n种物品和一个背包。物品种物品和一个背包。物品i的重量是的重量是wi，其价值为，其价值为vi，背包的容量为，背包的容量为C。应如何选择装。应如何选择装入背包的物品，使得装入背包中物品的总价值入背包的物品，使得装入背包中物品的总价值最大最大?在选择物品在选择物品i装入背包时，可
8、以选择物品装入背包时，可以选择物品i的的部分部分，而，而不一定要全部装入不一定要全部装入背包，背包，1in。不允许重复装入不允许重复装入。9ppt课件 于是，背包问题归结为寻找一个满足约束条于是，背包问题归结为寻找一个满足约束条件，并使目标函数达到最大的解向量件，并使目标函数达到最大的解向量X=(x1,x2,xn)。设设xi表示物品表示物品i装入背包的情况，根据问题的要求，装入背包的情况，根据问题的要求，有如下约束条件和目标函数：有如下约束条件和目标函数：)1(101nixCxwiniiiniiixv1max算法设计与分析算法设计与分析 贪心算法贪心算法10ppt课件每次捡最轻的物品装；每次捡
9、最轻的物品装；每次捡价值最大的装；每次捡价值最大的装；每次装包时既考虑物品的重量又考虑物品的每次装包时既考虑物品的重量又考虑物品的价值，也就是说每次捡单位价值最大的装。价值，也就是说每次捡单位价值最大的装。算法设计与分析算法设计与分析 贪心算法贪心算法贪心选择：贪心选择：只考虑到多装些物品，但由只考虑到多装些物品，但由于单位价值未必高，总价值于单位价值未必高，总价值不能达到最大；不能达到最大；每次选择的价值最大，但同时每次选择的价值最大，但同时也可能占用了较大的空间，装也可能占用了较大的空间，装的物品少，未必能够达到总价的物品少，未必能够达到总价值最大值最大确实能够达到总确实能够达到总价值最大
10、。价值最大。11ppt课件首先计算每种物品首先计算每种物品单位重量的价值单位重量的价值vi/wi，然，然后，依贪心选择策略，将尽可能多的后，依贪心选择策略，将尽可能多的单位重单位重量价值最高量价值最高的物品装入背包。的物品装入背包。若将这种物品全部装入背包后，背包内的物若将这种物品全部装入背包后，背包内的物品总重量未超过品总重量未超过C，则选择单位重量价值次高，则选择单位重量价值次高的物品并尽可能多地装入背包。的物品并尽可能多地装入背包。依此策略处理，直到背包装满为止。依此策略处理，直到背包装满为止。算法设计与分析算法设计与分析 贪心算法贪心算法基本步骤：基本步骤：12ppt课件算法设计与分析
11、算法设计与分析 贪心算法贪心算法void Knapsack(int n,float M,float v,float w,float x)/价值数组v1:n、重量数组w1:n;/它们元素的排列顺序满足vi/wivi+1/wi+1;/M是背包容量，x是解向量.float c=M;/使背包剩余容量初始化为M int i;Sort(n,v,w);for(i=1;i=n;i+)xi=0;/将解向量初始化为零 for(i=1;ic break;xi=1;c=c-wi;if(in )xi=c/wi;将各种物品依其单位重将各种物品依其单位重量的价值从大到小排序量的价值从大到小排序。算法的计算时间上界。算法的计
12、算时间上界为为O(nlogn)。13ppt课件n0-10-1背包问题：背包问题：给定给定n种物品和一个背包。物品种物品和一个背包。物品i的重量的重量是是wi，其价值为，其价值为vi，背包的容量为，背包的容量为C。应如何。应如何选择装入背包的物品，使得装入背包中物品选择装入背包的物品，使得装入背包中物品的总价值最大的总价值最大?在选择装入背包的物品时，对每种物品在选择装入背包的物品时，对每种物品 i只只有有2种选择，即装入背包或不装入背包。不能种选择，即装入背包或不装入背包。不能将物品将物品i装入背包多次，也装入背包多次，也不能只装入部分不能只装入部分的的物品物品i。算法设计与分析算法设计与分析
13、 贪心算法贪心算法14ppt课件算法设计与分析算法设计与分析 贪心算法贪心算法u对于0-1背包问题，贪心选择之所以不能得到最优解,是因为它无法保证最终能将背包装满，部分闲置的背包空间使每公斤背包空间的价值降低了。u事实上，在考虑0-1背包问题时，应比较选择该物品和不选择该物品所导致的最终方案，然后再作出最好选择。u由此就导出许多互相重叠的子问题。这正是该问题可用动态规划算法求解的另一重要特征。分析：分析：15ppt课件算法设计与分析算法设计与分析 贪心算法贪心算法4.3 4.3 最优装载最优装载 有一批集装箱要装上一艘载重量为有一批集装箱要装上一艘载重量为c的轮的轮船。其中集装箱船。其中集装箱
14、i的重量为的重量为wi。最优装载问题。最优装载问题要求确定在要求确定在装载体积不受限制装载体积不受限制的情况下，将的情况下，将尽可能多的集装箱装上轮船。尽可能多的集装箱装上轮船。问题描述问题描述cxinii 1w niix1max满足满足16ppt课件1.算法描述算法描述最优装载问题可用贪心算法求解。采用最优装载问题可用贪心算法求解。采用重量最轻者先装的贪心选择策略重量最轻者先装的贪心选择策略，可产生最，可产生最优装载问题的最优解。优装载问题的最优解。算法设计与分析算法设计与分析 贪心算法贪心算法17ppt课件算法设计与分析算法设计与分析 贪心算法贪心算法void Loading(int x,
15、Type w,float c,int n)int*t=new int n+1;Sort.(w,t,n);for(int i=0;i n&wti=c;i+)xti=1;c-=wti;ti中存储第中存储第i轻集装箱轻集装箱在原来序列中的下标在原来序列中的下标xi记载第记载第i个集装箱是个集装箱是否装入否装入,xi=1装入装入,xi=0未装入未装入18ppt课件物品重量分别为物品重量分别为15，10，27，18，船载重为，船载重为50定义：定义：w=15,10,27,18 物品重量物品重量 T =1,0,3,2 物品从轻到重排序后序号物品从轻到重排序后序号 C=50 船载重船载重贪心算法计算步骤：贪
16、心算法计算步骤：wT0=10c,c=c-10=40 wT1=15c,c=c-15=25 wT2=18c算法设计与分析算法设计与分析 贪心算法贪心算法例例19ppt课件算法设计与分析算法设计与分析 贪心算法贪心算法2.2.贪心选择性质贪心选择性质 设货箱已经从小到大排序，设货箱已经从小到大排序，是最优装载是最优装载问题的一个最优解，又设问题的一个最优解，又设),(21nxxx1|min1inixik如果给定的最优装载问题有解，则如果给定的最优装载问题有解，则1 k n（1）当）当k=1时，时，是一个满足贪婪选择是一个满足贪婪选择性质的最优解。性质的最优解。（2）当）当k 1时，时，则则 因此因此
17、，所给最优装载问题的一个可所给最优装载问题的一个可行解，且是最优解。行解，且是最优解。),(21nxxx,1,;0;11kinixyyyiik cxwxwwwywiniiiniikinii 1111),(21nyyy20ppt课件 设设 x1,.,xn 是最优装载问题的一个满足贪心选是最优装载问题的一个满足贪心选择性质的最优解，则择性质的最优解，则x1=1时时,x2,.,xn 是轮船载是轮船载重量为重量为c-w1且待装集装箱为且待装集装箱为 2,.,n时相应最优时相应最优装载问题的一个最优解。装载问题的一个最优解。算法设计与分析算法设计与分析 贪心算法贪心算法21ppt课件算法设计与分析算法设
18、计与分析 贪心算法贪心算法3.3.最优子结构性质最优子结构性质n最优装载问题具有最优子结构性质。最优装载问题具有最优子结构性质。n由最优装载问题的贪心选择性质和最优子结构性质由最优装载问题的贪心选择性质和最优子结构性质，容易证明算法的正确性。，容易证明算法的正确性。n算法的主要计算量在于将集装箱依其重量从小到大算法的主要计算量在于将集装箱依其重量从小到大排序，故算法所需的计算时间为排序，故算法所需的计算时间为 O(nlogn)。22ppt课件算法设计与分析算法设计与分析 贪心算法贪心算法 4.7 4.7 多机调度问题多机调度问题问题描述问题描述要求给出一种作业调度方案，使所给要求给出一种作业调
19、度方案，使所给的的n个作业在尽可能短的时间内由个作业在尽可能短的时间内由m台机器加工处台机器加工处理完成，作业理完成，作业i所需时间为所需时间为ti。约定，每个作业均。约定，每个作业均可在任何一台机器上加工处理，但未完工前不允可在任何一台机器上加工处理，但未完工前不允许中断，作业不能拆分成更小的子作业。许中断，作业不能拆分成更小的子作业。该问题是该问题是NP完全问题，到目前为止还没有有效的完全问题，到目前为止还没有有效的解法。用贪心选择策略有时可设计出较好的近似解法。用贪心选择策略有时可设计出较好的近似算法。算法。23ppt课件贪心近似算法贪心近似算法 采用采用最长处理时间作业优先最长处理时间
20、作业优先的贪心策略的贪心策略.当当nm时时,只要将机器只要将机器i的的0,ti时间区间时间区间分配给作业分配给作业i即可即可;当当nm时时,将将n个作业依其所需的处理时个作业依其所需的处理时间间从大到小排序从大到小排序，然后依次将作业分配给，然后依次将作业分配给空闲的处理机。空闲的处理机。算法设计与分析算法设计与分析 贪心算法贪心算法24ppt课件算法设计与分析算法设计与分析 贪心算法贪心算法class JobNode friend void Greedy(JobNode*,int,int);friend void main(void);public:operator int()const r
21、eturn time;private:int ID,time;class MachineNode friend void Greedy(JobNode*,int,int);public:operator int()const return avail;private:int ID,avail;多机调度问题的贪心近似算法多机调度问题的贪心近似算法作业结点类机器结点类25ppt课件templatevoid Greedy(Type a，int n，int m)if(n=m)cont”为每个作业分配一台机器为每个作业分配一台机器.“endl return；Sort(a，n)；/将作业按时间从大到小排序将作业按时间从大到小排序MinHeapH(m)；MachineNode x；for(int i=1；i=1；i-)/作业分配过程作业分配过程 HDeleteMin(x)；/从堆中取出堆顶从堆中取出堆顶x机器机器 cout”将机器将机器”xID“从从”xavail到到”(xavail十十aitime)”的时间段分配给作业的时间段分配给作业”ai.ID 贪心算法贪心算法 时间复杂度分析 nm 排序耗时O(nlogn)初始化堆O(m)DeleteMin 和Insert 耗时O(nlogm)共需时间为：O(nlogn+nlog m)=O(nlog n)27ppt课件
