算法设计与分析书中程序(第06章)

算法设计与分析书中程序(第06章)

ID:14389229

大小:790.50 KB

页数:7页

时间:2018-07-28

算法设计与分析书中程序(第06章)_第1页
算法设计与分析书中程序(第06章)_第2页
算法设计与分析书中程序(第06章)_第3页
算法设计与分析书中程序(第06章)_第4页
算法设计与分析书中程序(第06章)_第5页
资源描述:

《算法设计与分析书中程序(第06章)》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、【程序6-1】贪心法SolutionTypeGreedy(STypea[],intn){SolutionTypesolution=Æ;//初始时,解向量不包含任何分量for(inti=0;iclassK

2、napsack{public:Knapsack(intmSize,floatcap,float*wei,T*prof);//创建一维数组w和p,并赋初值voidGreedyKnapsack(float*x);//数组x为背包问题的最优解……private:floatm,*w;//m为背包载重量,w指示存储n个物品重量的数组T*p;//p指示存储n个物品收益的数组intn;//n为物品数目};templatevoidKnapsack::GreedyKnapsack(float*x){//前置条件:w[i]已按p[i]/w[i]的非增次序排列floatu=m;//u为背包剩余

3、载重量,初始时为mfor(inti=0;iu)break;x[i]=1.0;u=u-w[i];}if(i

4、d,int*x,intn){//设p0≥p1≥…≥pn-1intk=0;x[0]=0;for(intj=1;j=0&&d[x[r]]>d[j]&&d[x[r]]>r+1)r--;//搜索作业j的插入位置if((r<0

5、

6、d[x[r]]<=d[j])&&d[j]>r+1){//若条件不满足,选下一个作业for(inti=k;i>=r+1;i--)x[i+1]=x[i];//将x[r]以后的作业后移x[r+1]=j;k++;//将作业j插入r+1处}}returnk;}【程序6-5】使用并查集的带时限作业排序程序intFJS(int*d,i

7、nt*x,intn){UFSets(n);//创建由n棵树组成的并查集实例sintb,k=-1,*f=newint[n+1];for(inti=0;i<=n;i++)f[i]=i;//f[i]赋初值i,表示时限为i现分配时间片[i-1,i]for(i=0;i

8、Find(f[r]-1);//寻找时限为(f[r]-1)的树根ts.Union(t,r);//将t为根的树与r为根的树合并f[r]=f[t];//f[r]有f[t]的值}}delete[]f;//回收数组空间returnk;//(x[0],x[1],…,x[k])为解向量,长度为k+1·108·}【程序6-6】两路合并最佳模式的贪心算法templatestructHNode{//优先权队列中元素的类型operatorT()const{returnweight;}BTNode*ptr;Tweight;};templateBTNode*CreateHfm

9、Tree(T*w,intn){//w为一维数组保存n个权值PrioQueue>pq(2*n-1);//创建长度为2n-1的优先权队列实例pqBTNode*p;HNodea,b;//定义局部变量for(inti=0;i(w[i]);//创建一个合并树的新结点a.ptr=p;a.weight

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。