第7章 贪算法.ppt

?教学要求 了解贪心算法的概念与贪心算法设计要领 掌握应用贪心算法设计求解删数字问题、可拆背包问题与数列操作问题等最优化典型案例 ?本章重点 根据案例的实际选择与确定贪心策略;6.1 贪心算法概述;2. 贪心策略的选择;贪心算法的理论基础为拟阵，是组合优化与图论的重要内容。 若M是无向图G的拟阵，则S为图的边集，I是所有构成森林的一组边的子集。 如果对S的每一个元素X(X∈S)赋予一个正的权值W(X)，则称拟阵M=(S,I)为一个加权拟阵。 适宜于用贪心算法来求解的许多问题都可以归结为在加权拟阵中找一个具有最大权值的独立子集的问题，即给定一个加权拟阵M=(S,I)，若能找出一个独立且具有最大可能权值的子集A，且A不被M中比它更大的独立子集所包含，那么A为最优子集，也是一个最大的独立子集。 拟阵理论是一种能够确定贪心算法何时能够产生最优解的理论，虽然这套理论还很不完善，但在求解最优化问题时发挥着越来越重要的作用。 ; 7.2 删数字问题; 操作对象是一个可以超过有效数字位数的n位高精度数，存储在数组a中。 在整数的位数固定的前提下，让高位的数字尽量大，整数的值就大。这就是所要选取的贪心策略。 每次删除一个数字，选择一个使剩下的数最大的数字作为删除对象。选择这样“贪心”操作，是因为删k个数字的全局最优解包含了删一个数字的子问题的最优解。 当k=1时，在n位整数中删除哪一个数字能达到最大？从左到右每相邻的两个数字比较：若出现增，即左边数字小于右边数字，则删除左边的小数字。若不出现增，即所有数字全部降序或相等，则删除最右边的小数字。 ; 例如，在18位整数762191754639820463中，删除1个数字，使剩下的17位数最大，如何删？ 要使删除1个数字后的17位数最大，须首位数字最大。首先，首位数字“7”大于第2位数字“6”比较，首位数字“7”不能删！ 往后推，“6”与“2”比较，因62，为减，“6”不能删； 再往后推，“2”与“1”比较，因21,为减，“2”不能删 ； 继续往后推，“1”与“9”比较，因19，出现增，则删除左边的小数字“1”。 当k1（当然小于n），按上述操作,每一次操作???串首开始，每相邻的两个数字比较，出现“增”时，删除左边的小数字。每次操作删除一个数字后，后面的数字向前移位。 因此，只要从左至右每两相邻数字比较，出现“增”，即删除首数字。直到不出现“增”时，此时如果还不到删除指定的k位，打印剩下串的左边n?k个数字即可（相当于删除了余下的最右边若干个小数字）。;printf( 删除数字个数: );scanf(%d,k); i=0;m=0;x=0; while(kx m==0) {i=i+1; if(a[i-1]a[i]) // 两位比较出现递增,删除首数字 {printf(%d, ,a[i-1]); for(j=i-1;j=n-x-2;j++) a[j]=a[j+1]; x=x+1; i=0; // 从头开始查递增区间 } if(i==n-x-1) m=1; // 已无递增区间,m=1脱离循环 } if(xk) printf(及右边的%d个数字。\n,k-x); printf(\n 删除后所得最大数 );; 1）以上贪心删数字算法每删除一个数字a[i-1]，赋值i=0，即必须从头开始查找递增区间。其实此时只需从a[i-2]开始查找递增区间即可，因为先前的操作能够保证a[i-2]及之前的数字不是递增区间。 2）以上贪心删数字算法每删除一个数字a[i-1]，必须逐一把其后的数字往前移动一位，如果n及k相当大，移动过程花费较大。其实每删除数字后，并不一定需要移动数字的位置，只对所删除数位赋标记值-1即可，代表该位置的数字已经删除。同时，查找递增区间时跳过该数位。;7.3 埃及分数式;;; 以上贪心选择时，每一步都选比本分数小的最大埃及分数。这样尽管快速，但因为太严格可能会失去一些构建时机，或者可能根本找不到埃及分数式。 试把埃及分数贪心选择的环境适当放宽，选择范围适当扩大，即埃及分数的分母由以上贪心选择最小分母c=int(b/a)+1，扩展至c=int(b/a)+d，这里d为放宽尺度1,…,5等。必要时可把该尺度作扩大或缩小调整。;7.4 可拆背包问题;;// 已对n件物品按单位重量的效益降序排序 cw=c;s=0; // cw为背包还可装的重量 for(i=1;i=n;i++) {if(w[i]cw) break; x[i]=1.0; // 若w(i)=cw,整体装入