欢迎来到天天文库
浏览记录
ID:14389229
大小:790.50 KB
页数:7页
时间:2018-07-28
《算法设计与分析书中程序(第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(i4、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<05、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,i7、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;i8、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*CreateHfm9、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
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;i8、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*CreateHfm9、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
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
此文档下载收益归作者所有