计算机常用算法与程序设计教程（第2版）全套PPT课件.ppt

//已对n件物品按单位重量的效益降序排序cw=c;s=0; //cw为背包还可装的重量for(i=1;i=n;i++){if(w[i]cw)break;x[i]=1.0; //若w(i)=cw,整体装入cw=cw?w[i];s=s+p[i];}x[i]=(float)(cw/w[i]);//若w(i)cw,装入一部分)s=s+p[i]*x[i];3.贪心算法描述7.4构建埃及分数式案例提出：“埃及分数”为分子为1的分数。人们研究较多且颇感兴趣的问题是:把一个给定的分数转化为若干个不相同的埃及分数之和，约定埃及分数的分母不能与给定分数的分母相同。常把分解式中埃及分数的个数最少，或在个数相同时埃及分数中最大分母为最小的分解式称为最优分解式。对把给定分数分解为埃及分数之和，或对已有的埃及分数式进行优化，往往是一个繁琐艰辛的过程。例如，对3/11，可分解为:3/11=1/5+1/15+1/165试寻求分数3/11新的埃及分数式。1．贪心算法设计要点2．贪心算法设计步骤以上贪心选择时，每一步都选比本分数小的最大埃及分数。这样尽管快速，但因为太严格可能会失去一些构建时机，或者可能根本找不到埃及分数式。试把埃及分数贪心选择的环境适当放宽，选择范围适当扩大，即埃及分数的分母由以上贪心选择最小分母c=int(b/a)+1，扩展至c=int(b/a)+d，这里d为放宽尺度1,…,5等。必要时可把该尺度作扩大或缩小调整。3．贪心选择范围的扩展7.5.1数列压缩的最大值案例提出：给定一个由n个正整数组成的数列，对数列进行一次操作：去除其中两项a、b，然后添加一项a×b+1。每操作一次数列减少一项，经n?1次操作后该数列只剩一个数。试求在n-1次操作后最后得数的最大值。7.5数列压缩问题设数列有3项x，y，z(x≤y≤z)，由(x×y+1)×z+1≥(x×z+1)×y+1≥(y×z+1)×x+1可知选取数列中最小的2项操作，可使积最大。采用贪心算法，当数列中有3项以上时，为使最后所得数最大，每次选择去掉最小的2项操作。设置a数组存储数列各项，同时对n项进行升序排列。1.贪心算法设计要点为了得到最大值，设置控制n-1次操作的k（1——n-1）循环。每次操作对最小的前2项a[k]、a[k+1]实施操作：x=a[k];y=a[k+1];a[k+1]=x*y+1;操作后，应用逐项比较对a[k+1]，…，a[n]进行升序排列，为下一次操作做准备。最后所得a[n]即为所求的数列操作的最大值。因应用逐项比较进行排列，其时间复杂度为O(n^2)，因而数列操作的贪心设计的时间复杂度为O(n^3)。//先行对原始数据a数组升序排序for(k=1;k=n-1;k++)//共操作n-1次{x=a[k];y=a[k+1];a[k+1]=x*y+1;//实施一次操作for(i=k+1;i=n-1;i++)//操作后升序排列for(j=i+1;j=n;j++)if(a[i]a[j]){h=a[i];a[i]=a[j];a[j]=h;}}printf(\n最大值为：%ld\n,a[n]);2.贪心算法设计描述按贪心算法，每次操作只对最小的两项进行操作，因而无须对整个数列排序。我们只要把实施排序的2重循环for(i=k+1;i=n-1;i++)for(j=i+1;j=n;j++)改进为:for(i=k+1;i=k+2;i++)for(j=i+1;j=n;j++)这样，把原排序的时间复杂度O(n^2)降低为O(n)，于是整个数列操作的时间复杂度降低至O(n^2)。3.贪心算法设计优化6.20-1背包问题案例提出：1.动态规划设计逆推求解要点2)逆推计算最优值for(j=0;j=c;j++)if(j=w[n])m[n][j]=p[n];//首先计算m(n,j)elsem[n][j]=0;for(i=n?1;i=1;i??) //逆推计算m(i,j)for(j=0;j=c;j++)