4贪婪法

nullnull贪婪算法贪婪算法贪婪算法1 贪婪算法的思想 2 可绝对贪婪问题 3 相对贪婪问题 4 问题的复杂性 5 贪婪算法实例1 贪婪算法的思想1 贪婪算法的思想贪婪算法(贪心算法)的根本思想：最直接的方法：枚举；高效一点的方法：在生产该产品的每一道工序上都选择最省时的方法；以逐步的局部最优，达到最终的全局最优。贪婪算法通过一系列的局部选择来得到一个问题的解。所作的每一个选择都是当前状态下“最优”的选择。如何判断“当前最优”？要依照某种策略。策略“只顾眼前，不管将来”，称之为“贪婪策略”。贪婪算法没有固定的算法框架，算法的关键是贪婪策略的选择。贪婪算法能否得到最优解？例：求方法使生产某产品所花费的时间最少；1 贪婪算法的思想-例4.1-问题分析1 贪婪算法的思想-例4.1-问题分析例4.1 币种统计问题 某单位给每个职工发工资(精确到元)。为了保证不要临时兑换零钱，且取款的张数最少，取工资前要统计出所有职工的工资所需各种币值(100,50,20,10,5,2,1元共七种)的张数。请编程完成。1 贪婪算法的思想-例4.1-算法设计1 贪婪算法的思想-例4.1-算法设计数据结构记录最终币值所需数量：设置一个有7个元素的累加器数组S。若是同时处理多个人的工资(GZ)，则最好从数据库或文件读入GZ数据，再处理。本算法每次运行处理n个人的工资，从键盘输入GZ数额。贪婪策略： 对每个人的工资，用“贪婪”的思想，先尽量多地取大面额的币种，由大面额到小面额币种逐渐统计。将七种币值存储在数组B。这样，七种币值就可表示为B[i],i=1,2,3,4,5,6,7。为了能实现贪婪策略，七种币应该从大面额的币种到小面额的币种依次存储。 1 贪婪算法的思想-例4.1-算法实现1 贪婪算法的思想-例4.1-算法实现代码只需完全实现算法； 能否得到最优解由算法决定。main( ){ int i,j,n,GZ,A； int B[8]={0,100,50,20,10,5,2,1},S[8]; input(n); S[8]={0,0,0,0,0,0,0,0}; for(i=1;i<=n;i++){ input(GZ); for(j=1,j<=7;j++) { A=GZ/B[j]; S[j]=S[j]+A; GZ=GZ-A*B[j]; } } for(i=1;i<=7;i++) print(B[i], “----”, S[i]); }时间复杂度？嵌套的1->7循环与问题规模无关； O(n)。1 贪婪算法的思想-例4.1-不同情况1 贪婪算法的思想-例4.1-不同情况什么样的问题可以使用贪婪算法策略，并获得最优解？为什么？某国的币种是这样的,共9种:100,70,50,20,10,7,5,2,1。 这种情况下，刚才的贪婪算法是否能够求得最优解？因为，7、70破坏了“取最优”的贪婪策略的正确性。又为什么？在这样的币值种类下,再用贪婪算法就行不通了,比如某人工资是140,按贪婪算法140=100*(1张)+20*(2张)共需要3张,而事实上,只要取2张70面额的是最佳结果,这类问题可以考虑用动态规划算法来解决。1 贪婪算法的思想-例4.2 活动安排问题1 贪婪算法的思想-例4.2 活动安排问题 n个活动E={1,2,..,n}，都要求使用同一公共资源（如演讲会场等）。且在同一时间仅一个活动可使用该资源。 i[si,fi), si为起始时间, fi为结束时间。si=fj或sj > =fi 活动安排问题:求最大的相容活动子集合。 ---尽可能多的活动兼容使用公共资源。Sj fjSi fiSi fiSj fj1 贪婪算法的思想-例4.2 活动安排问题-算法1 贪婪算法的思想-例4.2 活动安排问题-算法1.按结束时间非减序排序:f1<=f2 <= .. <= fn --O(nlogn) 2.从第1个活动开始，按顺序放进集合A。放入活动i当且仅当与集合A中已有元素相容。 --与集合A中最后元素j比较：若si> =fj则加入，否则不加入 fj=max k  A（ fk）---集合A中的最大结束时间 A={a,b,d,f}S2 f2S1 f1S6 f6S4 f4Si fiS3 f3S5 f5 E={a,b,c,d,e,f}nullvoid GreedySelector(int n, int s[], int f[],bool A[]) { A[1]=true;// A[i]=true表示已被放入集合 int j=1; for (int i = 2; i <=n; i++) -O(n) { if (s[i]>=f[j]) { A[i]=true; j=i; } else A[i]=false; } }各活动的起始时间和结束时间存储于数组s和f中且按结束时间的非减序排列 当输入的活动已按结束时间的非减序排列，算法只需O(n)时间安排n 个活动，使最多的活动能相容地使用公共资源。 如果所给出的活动未按非减序排列，可以用O(nlogn)的时间重排。 1 贪婪算法的思想-例4.2 活动安排问题1 贪婪算法的思想-例4.2 活动安排问题规则：选择具有最早结束时间的相容活动加入，使剩余的可安排时间最大，以安排尽可能多的活动。 由于输入的活动以其完成时间的非减序排列，所以算法GreedySelector每次总是选择具有最早完成时间的相容活动加入集合A中。直观上，按这种方法选择相容活动为未安排活动留下尽可能多的时间。 也就是说，该算法的贪心选择的意义是使剩余的可安排时间段极大化，以便安排尽可能多的相容活动。 1 贪婪算法的思想-例4.2 活动安排问题1 贪婪算法的思想-例4.2 活动安排问题 例：设待安排的11个活动的开始时间和结束时间按结束时间的非减序排列如下： 例4.2 活动安排问题 算法GreedySelector的计算过程如左图所示。图中每行相应于算法的一次迭代。阴影长条表示的活动是已选入集合A的活动，而空白长条表示的活动是当前正在检查相容性的活动。1 贪婪算法的思想-例4.2 活动安排问题1 贪婪算法的思想-例4.2 活动安排问题 若被检查的活动i的开始时间Si小于最近选择的活动j的结束时间fi，则不选择活动i，否则选择活动i加入集合A中。 贪心算法并不总能求得问题的整体最优解。但对于活动安排问题，贪心算法GreedySelector却总能求得的整体最优解，即它最终所确定的相容活动集合A的规模最大。这个结论可以证明。 null贪心算法GreedySelector—总能得到整体最优解，即A规模最大。 证明： n个活动E={1,2,..,n}，按结束时间非减序排序:f1<=f2 <= .. <= fn。 1.总存在一个最优解以贪心选择开始即包含活动1。 E按结束时间非减序排序，活动1具有最早结束时间。 设A为最优解，AE,A也按结束时间非减序排序。 设A中第一活动为k，k=1时,显然成立。 k>1时,设B=A-{k}{1}，由于f1 <=fk,且A中活动互为相容，则B中活动也互为相容。 而B与A中活动个数相同，且A为最优解，则B为最优解。null2. 选择活动1以后，问题变为子问题E’:与活动1相容的活动安排问题。 设A为包含活动1的最优解，则A’=A-{1}为E’的一个最优解。 假如存在E’的一个解B’，|B’|>|A’|,则|B’ {1}|>A,与A为最优解矛盾。 由1,2 可知GreedySelector—总能得到整体最优解。 1 贪婪算法的思想-获得最优解的条件对于一个具体的问题，怎样知道是否可用贪心算法解此问题，以及能否得到问题的最优解呢? 这个问题很难给予肯定的回答。 从许多可以用贪心算法求解的问题中看到这类问题一般具有2个重要的性质：贪心选择性质和最优子结构性质。 1 贪婪算法的思想-获得最优解的条件1 贪婪算法的思想-获得最优解的条件1 贪婪算法的思想-获得最优解的条件贪婪选择性质贪心算法通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。 最优子结构性质指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。1 贪婪算法的思想-获得最优解的条件1 贪婪算法的思想-获得最优解的条件 如图，有4个点，分别是A、B、C、D，相邻两点用两条连线C2k,C2k-1(1≤k≤3)表示两条通行的道路。连线上方的数字表示道路长度。定义从A到D所有路径中，长度除以4所得余数最小的路径为最优路径。求一条最优路径。 在本题中，如果按照最优子结构的思维来求解就会发生错误。例如，A最优取值可以由B的最优取值来确定，而B的最优取值为0，所以A的最优值为2，而实际上，路径C1—C3—C5可得最优值为0，所以，B的最优路径并不是A最优路径的子路径，也就是说，A的最优取值不是由B的最优取值决定的，其不具有最优子结构。不具有最优子结构例子：1 贪婪算法的思想-

总结

初级经济法重点总结下载党员个人总结TXt高中句型全总结.doc高中句型全总结.doc理论力学知识点总结pdf

1 贪婪算法的思想-总结适用问题 两类 可绝对贪婪问题 求最优解； 具有贪婪选择性质、最优子结构性质； 相对贪婪问题 求近似解； 不具备全部性质，但求解效率要求高，解的精度要求不高。得到近似解不算彻底解决问题。算法框架 核心：贪婪策略2 可绝对贪婪问题-例4.32 可绝对贪婪问题-例4.3例4.3 键盘输入一个高精度的正整数N，去掉其中任意S个数字后剩下的数字按原左右次序将组成一个新的正整数。编程对给定的N和S，寻找一种

方案

气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载

使得剩下的数字组成的新数最小。 输出应包括所去掉的数字的位置和组成的新的正整数(N不超过100位)。数据结构设计：和上一节对高精度正整数的处理一样，将输入的高精度数存储为字符串格式。根据输出要求设置数组，在删除数字时记录其位置。2 可绝对贪婪问题-例4.3-问题分析2 可绝对贪婪问题-例4.3-问题分析贪婪策略n1=“1 2 4 3 5 8 6 3”在位数固定的前提下，让高位的数字尽量小其值就较小；删除高位较大的数字；具体地相邻两位比较若高位比低位大则删除高位。通过“枚举归纳”设计算法，实例(s=3) ： n1=“1 2 4 3 5 8 6 3”4比3大 删除 “1 2 3 5 8 6 3”8比6大 删除 “1 2 3 5 6 3”6比3大 删除 “1 2 3 5 3”2 可绝对贪婪问题-例4.3-问题分析2 可绝对贪婪问题-例4.3-问题分析再一个实例： n2=“2 3 1 1 8 3”由实例1，相邻数字只需要从前向后比较；而从实例2中可以看出当第i位与第i+1位比较，若删除第i位后，必须向前考虑第i-1位与第i+1位进行比较，才能保证结果的正确性。3比1大 删除 “2 1 1 8 3”2比1大 删除 “ 1 1 8 3”8比3大 删除 “ 1 1 3”2 可绝对贪婪问题-例4.3-问题分析2 可绝对贪婪问题-例4.3-问题分析n3=”1 2 3 4 5 6 7” s=3n4=”1 2 0 0 8 3” s=3由这个实例子又能看出，当删除掉一些数字后，结果的高位有可能出现数字“0”，直接输出这个数据不合理，要将结果中高位的数字“0” 删除掉，再输出。特别地还要考虑若结果串是“0000”时，不能将全部“0”都删除，而要保留一个“0”最后输出。由这个实例看出，经过对n3相邻比较一个数字都没有删除，这就要考虑将后三位进行删除；当然还有可能，在相邻比较的过程中删除的位数小于s时，也要进行相似的操作。2比0大 删除 “1 0 0 8 3”1比0大 删除 “ 0 0 8 3”8比3大 删除 “ 0 0 3”2 可绝对贪婪问题-例4.3-算法设计2 可绝对贪婪问题-例4.3-算法设计算法设计： 根据以上实例分析，算法主要由四部分组成：初始化、相邻数字比较(必要时删除)、处理比较过程中删除不够s位的情况和结果输出。 1)物理进行字符删除，就是用后面的字符覆盖已删除的字符，字符串长度改变。这样可能会有比较多字符移动操作，算法效率不高。2) 可以利用数组记录字符的存在状态，元素值为“1”表示对应数字存在，元素值为“0”表示对应数字已删除。这样避免了字符的移动，字符串长度不会改变，可以省略专门记录删除数字的位置。但这样做前后数字的比较过程和最后的输出过程相对复杂一些。其中删除字符的实现方法很多，如：2 可绝对贪婪问题-例4.3-算法设计2 可绝对贪婪问题-例4.3-算法设计3)同样还是利用数组，记录未删除字符的下标，粗略的过程如下： n=“1 2 4 3 5 8 3 3” s=3 1 2 3 4 5 6 7 8 4比3大 删除 “1 2 4 3 5 8 3 3” 1 2 4 5 6 7 8 8比3大 删除 “1 2 4 3 5 8 3 3” 1 2 4 5 7 85比3大 删除 “1 2 4 3 5 8 3 3” 1 2 4 7 8这时数组好象是数据库中的索引文件。此方式同样存在操作比较复杂的问题。null算法设计1： 一种简单的控制相邻数字比较的方法是每次从头开始，最多删除s次，也就从头比较s次。按题目要求设置数组data记录删除的数字所在位置。 delete(char n[],int b,int k) { int i; for(i=b;i<= length(n)-k;i=i+1) n[i]=n[i+k]; } nullmain（） {char n[100]; int s,i,j,j1,c,data[100],len; input(n); input(s); len=length(n); if(s>len) {print(“data error”); return;} j1=0; for (i=0;i<=s ;i=i+1) {for (j=1;j<=length(n);j=j+1) if (n[j]>n[j+1]) //贪婪选择 { delete(n,j,1); if (j>j1) data[i]=j+i; //记录删除数字位置 else data[i]=data[i-1]-1; //实例2向前删除的情况 j1=j; break; } if( j>length(n)) break;} for (i=i;i<=s;i=i+1) { j=len-i+1;delete(n,j,1); data[i]=j;} while (n[1]='0' and length(n) >1) delete(n,1,1); //将字符串首的若干个“0”去掉 print(n); for (i=1;i<=s;i=i+1) print(data[i],' '); }i控制删除字符的个数j控制相邻比较操作的下标null算法设计2： 删除字符的方式同算法1，只是删除字符后不再从头开始比较，而是向前退一位进行比较，这样设计的算法2的效率较算法1要高一些。delete( )函数同前。 变量i控制删除字符的个数，变量j控制相邻比较操作的下标，当删除了第j个字符后，j赋值为j-1，以保证实例2（字符串n2）出现的情况得到正确处理。 nullmain(){ char n[100]; int s,i,j,j1,data[100],len; input(n); input(s); len=length(n); if(s>len){ print(“data error”); return; } i=0; j=1; j1=0; while(ij1) data[i]=j+i; else data[i]=data[i-1]-1; i=i+1; j1=j; j=j-1; } } for (i=i;i<=s;i=i+1){ j=len-i+1; delete(n,j,1); data[i]=j; } while (n[1]='0' and length(n) >1) delete(n,1,1); print(n); for (i=1;i<=s;i=i+1) print(data[i],' '); } delete(char n,int b,int k){ int i; for(i=b;i<= length(n)-k;i=i+1) n[i]=n[i+k]; }2 可绝对贪婪问题-例4.4 数列极差问题2 可绝对贪婪问题-例4.4 数列极差问题　 例4.4 在黑板上写N个正整数排成一个数列，进行如下操作:每一次擦去其中的两个数a和b，然后在数列中加入一个数a×b+1，如此下去直至黑板上剩下一个数，在所有按这种操作方式最后得到的数中，最大的记作max，最小的记作min，则该数列的极差定义为M=max-min。 2 可绝对贪婪问题-例4.4-问题分析通过实例来认识题目中描述的计算过程。 对三个具体数据3，5，7讨论，可能有以下三种结果： (3*5+1)*7+1=113,(3*7+1)*5+1=111, (5*7+1)*3+1=109 结论：先运算小数据得到的是最大值，先运算大数据得到的是最小值。 2 可绝对贪婪问题-例4.4-问题分析null 下面以三个数为例证明此题用贪心策略求解的合理性,不妨假设：a0，则有以下几种组合计算结果： 1)(a*b+1)*c+1=a*a*a+(2k1+k2)a*a+(k1(k1+k2)+1)*a+k1+k2+1 2)(a*c+1)*b+1=a*a*a+(2k1+k2)a*a+(k1(k1+k2)+1)*a+k1+1 3)(b*c+1)*a+1=a*a*a+(2k1+k2)a*a+(k1(k1+k2)+1)*a+1 显然此问题适合用贪婪策略,不过在求最大值时，要先选择较小的数操作。求最小值时，要先选择较大的数操作。这是一道两次运用贪心策略解决的问题。 2 可绝对贪婪问题-例4.4-算法设计1）不断从现有的数据中，选取最大和最小的两个数，计算后的结果继续参与运算，直到剩余一个数算法结束。 2) 选取最大和最小的两个数较高效的算法是用二分法完成， 这里仅用简单的逐个比较方法来求解。注意到由于找到的两个数将不再参与其后的运算，其中一个用它们的计算结果代替，另一个用当前的最后一个数据覆盖即可。所以不但要选取最大和最小，还必须记录它们的位置，以便将其覆盖。 3）求max、min过程必须独立，即求max和min都必须从原始数据开始,否则不能找到真正的max和min。 2 可绝对贪婪问题-例4.4-算法设计null 1)由设计2）、3）知，必须用两个数组同时存储初始数据。 2)求最大和最小的两个数的函数至少要返回两个数据，方便起见用全局变量实现。 int s1,s2; main（ ） {int j,n,a[100],b[100],max,min; print(“How mang data?”); input(n); print(“input these data”); for (j=1;j<=n;j=j+1) {input(a[j]); b[j]=a[j];} min= calculatemin(a,n); max= calculatemax(b,n); print(“max-min=”, max-min) }nullcalculatemin(int a[],int n) { int j; while (n>2) { max2(a,n); a[s1]= a[s1]* a[s2]+1; a[s2]=a[n]; n=n-1;} return(a[1]* a[2]+1); } max2(int a[],int n) { int j; if(a[1]>=a[2]) { s1=1; s2=2;} else { s1=2; s2=1;} for (j=3;j<=n;j++) { if (a[j]>a[s1]) { s2=s1; s1=j;} else if (a[j]>a[s2]) s2=j; } } null calculatemax(int a[],int n) { int j; while (n>2) { min2(a,n); a[s1]= a[s1]* a[s2]+1; a[s2]=a[n]; n=n-1;} return(a[1]* a[2]+1); } min2(int a[ ],int n) { int j; if(a[1]<=a[2]) { s1=1; s2=2;} else { s1=2; s2=1;} for (j=3;j<=n;j++) if (a[j]1/2， 7/8-1/2>1/3， 7/8-1/2-1/3=1/24。 过程如下： 1)找最小的n（最大的埃及分数1/n），使分数f>1/n； 2)输出1/n； 3)计算f=f-1/n； 4)若此时的f是埃及分数，输出f,算法结束,否则返回1）。2 可绝对贪婪问题-例4.5-问题模型记真分数F=A/B；对B/A进行整除运算,商为D,余数为0＜K＜A，它们导出关系如下： B=A*D+K,B/A=D+K/A＜D+1,A/B＞1/(D+1),记C=D+1。 这样分数F所包含的“最大”埃及分数就是1/C。 进一步计算：A/B-1/C=（A*C-B）/B*C 也就是说继续要解决的是有关分子为A=A*C-B,分母为B=B*C的问题。2 可绝对贪婪问题-例4.5-问题模型2 可绝对贪婪问题-例4.5-算法设计由以上数学模型，算法过程如下： 1)设某个真分数的分子为A(≠1），分母为B； 2)把B除以A的商的整数部分加1后的值作为埃及 分数的一个分母C； 3)输出1/C； 4)将A乘以C减去B作为新的A； 5)将B乘以C作为新的B； 6)如果A大于1且能整除B,则最后一个分母为B/A； 7)如果A＝1,则最后一个分母为B；否则转步骤2)。2 可绝对贪婪问题-例4.5-算法设计null实例：7/8=1/2+1/3+1/24的解题步骤： 同样用变量A表示分子，变量B表示分母； C=8/7+1=2 //说明7/8>1/2， 打印1/2 A=7*2-8=6,B=B*C=16 //计算7/8-1/2=(7*2-8)/(7*2)=6/16=A/B C=16/6+1=3 //说明16/6>1/3， 打印1/3 A=6*3-16=2,B=B*C=16*3=48 //计算6/16-1/3=(6*3-16)/(16*3)=2/48=A/B A>1但B/A为整数24，打印1/24 结束。2 可绝对贪婪问题-例4.5-算法main( ) { int a,b,c; print(“input element”); input(a); print(“input denominator”); input(b); if(a>=b) print(“input error”); else if (a=1 or b mod a=0) print( a, "/",b, "=" 1, "/",b/a); else   while(a<>1) { c = b /a + 1     a = a * c – b; b = b * c;     print( "1/",c);     if( a > 1) print("+"); if (b mod a =0 ) { print ("1/"; b / a); a=1; } }    } 2 可绝对贪婪问题-例4.5-算法3 相对贪婪问题-例4.6-取数游戏3 相对贪婪问题-例4.6-取数游戏 有2个人轮流取2n个数中的n个数，取数之和大者为胜。请编写算法，让先取数者胜，模拟取数过程。 3 相对贪婪问题-例4.6-问题分析 这个游戏一般假设取数者只能看到2n个数中两边的数,用贪婪算法的情况: 若一组数据为：6,16,27,6,12,9,2,11,6,5。用贪婪策略每次两人都取两边的数中较大的一个数,先取者胜。 以A先取为例，取数结果： A 6,27,12,5,11=61 胜 B 16,6,9,6,2=393 相对贪婪问题-例4.6-问题分析3 相对贪婪问题-例4.6-问题分析 若选另一组数据：16,27,7,12,9,2,11,6。仍用贪婪算法，先取者A败。 取数结果： A 16,7,9,11=43 B 27,12,6,2=47 胜 若只能看到两边的数据，则此题无论先取还是后取都无必胜的策略。这时一般的策略是用近似贪婪算法。 但若取数者能看到全部2n个数，则此问题可有一些简单的方法，有的虽不能保证所取数的和是最大，却是一个先取者必胜的策略。3 相对贪婪问题-例4.6-问题分析3 相对贪婪问题-例4.6-数学模型数学模型：N个数排成一行，从左到右编号，依次为1，2，…，N，因为N为偶数，又因为我们先取数，计算机后取数，所以一开始我们既可取到一个奇编号数，又可取到一个偶编号数。 若我们第一次取奇编号数，则计算机只能取到偶编号数； 若我们第一次取偶编号数，则计算机只能取到奇编号数； 所以，只要比较奇编号数之和与偶编号数之和谁大，以决定最开始我们是取奇编号数还是偶编号数即可。（若同样大，我们第一次可任意取数，因为当两和相同时，先取者胜。） 3 相对贪婪问题-例4.6-数学模型3 相对贪婪问题-例4.6-算法设计算法设计：只需分别计算一组数的奇数位和偶数位的数据之和，然后先取数者可以确定必胜的取数方式。 以下面一排数为例：1 2 3 10 5 6 7 8 9 4 奇编号数之和为25（=1+3+5+7+9），小于偶编号数之和为30（=2+10+6+8+4）。我们第一次取4，以后，计算机取哪边数我们就取哪边数（如果计算机取1，我们就取2；如果计算机取9，我们就取8）。这样可保证我们自始自终取到偶编号数，而计算机自始自终取到奇编号数。 3 相对贪婪问题-例4.6-算法设计nullmain( ) { int i,s1,s2,data; input(n); s1=0； s2=0; for(i=1;i<=n;i=i+1) { input( data); if (i mod 2=0) s2=s2+data; else s1=s1+data; if(s1>s2) print(“first take left”); else print(“first take right”); 结论：解决问题时数学模型的选择是非常重要的。3 相对贪婪问题-例4.7-多机调度问题3 相对贪婪问题-例4.7-多机调度问题设有n个独立的作业{1,2,…, n }，由m台相同的机器进行加工处理。 作业i所需的处理时间为ti 。现约定，每个作业均可在任何一台机器上加工处理，但未完工前不允许中断处理。作业不能拆分成更小的子作业。 多机调度问题要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。3 相对贪婪问题-例4.7-问题分析3 相对贪婪问题-例4.7-问题分析这个问题是“NP完全问题”，到目前为止还没有“有效”的解法。对于这一类问题,用贪心选择策略有时可以设计出较好的近似算法。采用最长处理时间作业优先的贪心选择策略可以设计出解多机调度问题的较好的近似算法。 按此策略，当m<=n 时，只要将机器i的[0, ti ]时间区间分配给作业i即可。 当m > n 时，首先将n个作业依其所需的处理时间从大到小排序。然后依此顺序将作业分配给空闲的处理机。3 相对贪婪问题-例4.7-算法实现3 相对贪婪问题-例4.7-算法实现例如，设7个独立作业{1,2,3,4,5,6,7}由3台机器M1，M2和M3加工处理。各作业所需的处理时间分别为{2,14,4,16,6,5,3}。 计算结果：所需的加工时间为17。 1 先将n个作业从小到大排序，存入数组a； 2 将排好序的后m个作业按照从小到大存入数组b； 3 循环 n-m次，将 a中剩余的最大项(从a[n-m]到a[1] )与b中最小项相加； 在计算过程中输出分配情况，b中最大元素为加工时间。4 问题的复杂性4 问题的复杂性算法的复杂性 解决问题的一个具体算法的执行时间，这是算法的性质；P39问题的复杂性 问题本身的复杂程度。所有可计算的问题都是实际可被计算机计算的吗？对于这个问题的准确理解需要理解计算模型“图灵机”。下面的概念定义仅算“科普”级。可以解决问题的算法的最低复杂度。 若一个问题有多项式级的算法，则称该问题复杂度为多项式时间。4 问题的复杂性-有效的算法4 问题的复杂性-有效的算法所有可计算的问题都是实际可被计算机计算的吗？共识：复杂性为O(nk)的算法是“有效”的算法。k为正整数。指数级，阶乘级的算法均非有效的算法。所有问题都有“有效的算法”吗？4 问题的复杂性-问题分类4 问题的复杂性-问题分类不一定。所有问题都有“有效的算法”吗？P类问题， 多项式问题：所有复杂度为多项式时间的问题的集合，称这类问题为易解的问题。NP类问题，非确定的多项式问题：包含所有没有找到多项式时间算法的问题的集合。无法证明一定没有。NPC类问题，NP完全问题：要么每个NP完全问题都存在多项式时间的算法(即通常所指的有效算法)；要么所有NP完全问题都不存在多项式时间的算法。4 问题的复杂性-分类图4 问题的复杂性-分类图5 贪婪算法实例-例4.8-背包问题森林里进行一场装背包比赛： 参加者：猴子 黑熊 啄木鸟 每个比赛者一个背包，背包的载重量为20公斤。 给定N个物品，每个物品有一定的重量和价值。20kg5 贪婪算法实例-例4.8-背包问题5 贪婪算法实例-例4.8-背包问题 森林里进行一场装背包比赛 规则： 物品可切一部分放入； 背包里装的物品的总重量不超过背包的载重量； 背包里装的物品的价值最高者获胜。5 贪婪算法实例-例4.8-背包问题黑瞎子掰棒子的策略黑瞎子掰棒子的策略黑熊 黑瞎子掰棒子的策略：价值高的优先放入。 物品n=3，背包的载重量C=20 各个物品的价值(v1,v2,v3)=(25,24,15) 各个物品的重量( w1,w2,w3)=(18,15,10)。物品1 物品2 1 2/15物品2 2/15物品2 48/15物品2 2重量20价值28.2物品1物品1 18 物品1 25 猴子耍小聪明策略猴子耍小聪明策略猴子 耍小聪明策略：重量小的优先放入。 物品n=3，背包的载重量C=20 各个物品的价值(v1,v2,v3)=(25,24,15) 各个物品的重量( w1,w2,w3)=(18,15,10)。物品3 物品2 1 2/3物品2 10/15 物品2 16 物品2 10 重量20价值31物品3物品3 10 物品3 15 啄木鸟算盘子策略啄木鸟算盘子策略 啄木鸟 算盘子策略：单位重量价值高的优先放入。 物品n=3，背包的载重量C=20 (v1,v2,v3)=(25,24,15) ( w1,w2,w3)=(18,15,10) (v1/w1, v2/w2, v3/w3)=(1.39,1.6,1.5)物品2 物品3 1 1/2物品3 1/2物品3 7.5 物品3 5 重量20价值31.5物品2物品2 15物品2 24啄木鸟算盘子策略啄木鸟算盘子策略啄木鸟算盘子策略的时间复杂度?第一步:选出单位重量价值最高者装入。 n个中取最大值 第二步：删除该物品。 第三步:重复1,2步,直至再装入就超出背包的载重量为止。 第四步:把最后选择物品的一部分装入背包: 剩余载重量/最后选择物品的重量O(n)O(n2)O(n)啄木鸟算盘子策略啄木鸟算盘子策略能否改进? 时间复杂度? 第一步:按照单位重量价值递减排序。 n个数排序 第二步:按排序顺序依次装入直至再装入就超出背包的 载重量为止。 第三步:把最后选择物品的一部分装入背包: 剩余载重量/最后选择物品的重量O(nlogn)O(nlogn)O(n)背包问题背包问题 该问题就是背包问题： 已知：给定n种物品和一个背包。 物品i重量是Wi，其价值为Vi，背包容量为C。 求解：如何选择装入背包的物品，使得装入背包中物品总价值最大? 背包问题的形式化描述背包问题的形式化描述每个物品xi 可以不被装入背包，也可以部分装入背包, 0≤xi≤1 每个物品的价值和重量值都大于0，总共有1个或者n个物品，vi>0，wi>0，1≤i≤n 约束条件:背包载重量是C，因此选入背包中物品的总重量不得超过C背包问题背包问题问题的求解目标:背包中的物品总价值最大。 目标函数: max 啄木鸟的选择是否使总价值最大?最优解的证明最优解的证明第一步证明: 首先选择单位重量价值最高的物品装入是正确的。 假设物品已按单位重量价值递减顺序排序且w1A’+V1=A 这与A为原问题的最优解相矛盾。　 最优解的证明最优解的证明第一步选择正确。 选择后的子问题的最优解为A-W1。 由归纳法可证明,经这样的选择最终得到原问题的最优解。 V1 V1….. Vk V1….. Vk . …VjV1V1+..+Vk用贪心法求解背包问题的分析 用贪心法求解背包问题的分析 黑熊策略:目标函数作为度量

标准

excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载

。此标准虽然使一个物品产生最大价值效益，但是它消耗载重量空间过快。 猴子策略:使背包载重量尽可能慢地被消耗作标准。此标准虽然使背包的载重量消耗慢了，但是背包的价值却没有能够迅速地增加。 啄木鸟策略: 把二者综合起来，以单位重量中的最大价值(尽可能多的单位价值高的物品装入)作为衡量标准，即考虑vi/wi的值，使所占用的单位重量所带来的价值最大。因此把vi/wi的值按降序排序，vi/wi最高的首先放入背包，vi/wi次高的接着放入背包，依此类推。贪心法解题总结贪心法解题总结首先选取一个度量标准（贪婪准则），以这个标准把这n个输入排序，并按排序顺序一次输入一个量。然后把这个新的输入与当前已构成的在这种度量意义下的部分解加在一起，考察新增这个输入后是否能够产生一个可行解，如果不能则不把这个输入加入到这部分已经存在的可行解中(贪心选择)。 用贪心法处理问题的核心是度量标准的选取。需要指出的是把目标函数作为度量标准得到的解并不一定是问题的最优解。5 贪婪算法实例-例4.95 贪婪算法实例-例4.9例4.9 huffman编码 huffman树的构造算法null 基本概念： 路径：从树中一个结点到另一个结点之间的分支构成这两个结点 间的路径。 结点的路径长度：两结点间路径上的分支数。 树的路径长度：从树根到每一个结点的路径长度之和。记作：TL 从根 A 到 B，C，D，E， F，G，H，I 的路径长度 分别为 1，1，2，2，3， 3，4，4。 TL（a）＝0＋1＋1＋2＋2＋3＋3＋4＋4＝20 TL（b）＝0＋1＋1＋2＋2＋2＋2＋3＋3＝16 完全二叉树是路径长度最短的二叉树。 null权：将树中结点赋给一个有着某种含义的数值，则这个数值 称为该结点的权。 结点的带权路径长度：从根结点到该结点之间的路径长度与该结点的权的乘积。树的带权路径长度：树中所有叶子结点的带权路径长度之和。 记作： 权值 结点到根的路径长度 null例：有4 个结点 a, b, c, d，权值分别为 7, 5, 2, 4，试构造以此 4 个结点为叶子结点的二叉树。 WPL=72+52+22+42= 36WPL=71+52+23+43= 35 WPL=71+52+23+43= 35 WPL=73+53+21+42= 46 哈夫曼树 具有相同带权结点构成的哈夫曼树不惟一。 满二叉树不一定是哈夫曼树。 null哈夫曼树： 因为构造这种树的算法是由哈夫曼于 1952 年提出的， 所以被称为哈夫曼树，相应的算法称为哈夫曼算法。 带权路径长度 (WPL) 最短的二叉树 （权值大的结点离根最近） 目标null哈夫曼算法口诀： 1、构造森林全是根； 2、选用两小造新树； 3、删除两小添新人； 4、重复 2、3 剩单根。 例：有4 个结点 a, b, c, d，权值分别为 7, 5, 2, 4，构造哈夫曼树。 哈夫曼树的结点的 度数为 0 或 2， 没 有度为 1 的结点。null例：有4 个结点 a, b, c, d，权值分别为 7, 5, 2, 4，构造哈夫曼树。 贪婪策略每次合并两棵具有最小权值的树，新树权值为两树之和；满足贪婪选择性质；需证明：设NodeSet是结点集合，其中结点i的权值是w(i)，又设x，y是NodeSet中具有最小权值的两个节点，则存在NodeSet组成的一个huffman树，使x，y是最深叶子且为兄弟。null1.证明：具有贪心选择性质 设二叉树T是一颗huffman树。b、c是二叉树T的最深叶子且为兄弟。不失一般性，设w(b)≤w(c)，设x、y是NodeSet中权值最小的两结点， w(x)≤w(y)，则有w(x) ≤ w(b)， w(y)≤w(c) 在树T中交换叶子b和x的位置得到树T’，再交换叶子c和y的位置，得到树T’’。 带权路径长度：WPL(T)=iT w(i)TL(c) i—二叉树上的结点 w(i)—结点i的权值 TL（i）--结点i的路径长度TxybcT’’bcxyT’byxcnullWPL(T)-WPL(T’)= iT w(i) TLT(i) -iT w(i)TLT’(i) = w(x)TLT(x)+w(b)TLT(b)-w(x)TLT’(x) –w(b)TLT’(b) = w(x)TLT(x) –w(x)TLT(b) +w(b)TLT(b)-w(b)TLT(x) = (w(b)-w(x))(TLT(b)- TLT(x)) ≥0 同理： WPL(T’)-WPL(T’’) ≥0 // TLT(b)=TLT’(x) 则 WPL(T’’) ≤ WPL(T’) ≤ WPL(T) 又T是哈夫曼树。 WPL(T) ≤WPL(T’’) 则 WPL(T )=WPL(T’’)。 T’’是含最小权值结点的哈夫曼树，x和y为最深叶结点且为兄弟。 TxybcT’’bcxyT’byxcnull例：有4 个结点 a, b, c, d，权值分别为 7, 5, 2, 4，构造哈夫曼树。 子结构设T是表示NodeSet的huffman树，设x，y是两个叶子结点，且互为兄弟，z是它们的父亲。若将z看成权值为w(z)=w(a)+w(b)的结点，则对于： 树T ’=T - {x，y } ，结点集合N ’ = NodeSet -{x，y}U{ z}， T ’是N ’的huffman树，是原问题的子结构。 满足最优子结构性质。可以证明。null2.证明：具有最优子结构性质 二叉树T是哈夫曼树。x、y是二叉树T的最深叶子且为兄弟。 设z为其父亲，w(z)=w(x)+w(y)，则树T’=T-{x，y}是结点集合 N’=NodeSet-{x，y}{z}的哈夫曼树。 证明：反证法。 由已知不难得出，TLT(x)=TLT(y) = TLT’(z)+1 对任意的i NodeSet-{x，y}，有 TLT’(i)=TLT(i) WPL(T)-WPL(T’) = iN w(i)TLT(i)- iN’ w(i)TLT’(i) = w(x)TLT(x)+w(y)TLT(y)- w(z)TLT’(z) = (w(x)+w(y)) TLT’(z) + w(x)+w(y) – w(z)TLT’(z) = w(x)+w(y)null假定T’不是结点集合N’ 的哈夫曼树，则存在结点集合N’ 的哈夫曼树，设为T’’。则有WPL(T’)>WPL(T’’) z是T’’中的一个叶子，将x,y 加入作为z的儿子，得到结 点集合N的二叉树T’’’。 WPL(T’’’) = iN’ w(i)TLT’’(i)+w(x)(TLT’’(z)+1)+ w(y)(TLT’’(z)+1) - w(z)TLT’’(z) = iN’ w(i)TLT’’(i)+w(x)+w(y) ≤WPL(T’)+ w(x)+w(y) =WPL(T) 与T是结点集合N的哈夫曼树矛盾。T’’’zbcxyT’’zbcxy5 贪婪算法实例-例4.105 贪婪算法实例-例4.10例4.10 单源最短路径—Dijkstra算法给定一个带权有向图G=（V，E），V={1,2,…,n }，其中每条边的权是一个非负实数。给定一个顶点 v，称为源。 单源最短路径问题：求从源到各顶点的最短路长度（路径上各边权之和）。null实例 13 (v0, v1) (v0, v2) (v0, v2, v3) (v0, v2, v3, v4) (v0, v2, v3, v4, v5) (v0, v1, v6) 8 13 19 21 20 null 路径长度最短的最短路径的特点： 在此路径上，必定只含一条弧 ，且其权值最小。 它只可能有两种情况： 1)、直接从源点到 v2 < v0, v2> （只含一条弧）； 2)、从源点经过顶点 v1，再到达 v2 < v0, v1>, < v1, v2> （由两条弧组成）。 下一条路径长度次短的最短路径的特点： , null 可能