..-PAGE2-优选--.-总结资料-?算法设计?课程报告课题名称：算法设计课题负责人名〔学号〕：---同组成员〔角色〕：---指导教师：---评阅成绩：评阅意见：提交报告时间：2021年6月17日最小重量机器设计问题计算机科学与技术专业学生--指导教师---[题目描述]设某一机器由n个部件组成，每一种部件都可以从m个不同的供给商处购得。高wij是从供给商j处购得的部件i的重量，cij是相应的价格。试设计一个算法，给出总价格不超过c的最小重量机器设计。编程任务：对于给定的机器部件重量和机器部件价格，编程计算总价格不超过d的最小重量机器设计。数据输入：由文件input.txt给出输入数据。第一行有3个正整数n，m和d。接正业的2n行，每行n个数。前n行是c，后n行是w。结果输出：将计算出的最小重量，以及每个部件的供给商输出到文件output.txt。输入文件例如输出文件例如input.txtoutput.txt3344123131321222123321222[算法分析]采用回溯算法和分支定界法分别实现，对于回溯法，采用深度优先搜索对子集树进展剪枝，剪枝条件是当前的总费用不超过总费用；对于分支定界法，采用按照层次遍历对子集树进展剪枝，并将每层的结点按照重量由小到大进展排序，将相应下标保存在二维数组s中，以便构造最优解。两种算法是时间复杂度都是O(m^n)，空间复杂度均为O(nm)，但由于分支定界法在已经排好序的序列中查找，因此查找到的第一个解即为最优解，理论上来说，时间效率会比回溯法高。[程序实现]回溯法代码#include
#include#include#include#include#includeusingnamespacestd;#defineINF999999999#defineMAXSIZE100+1intcur_solution[MAXSIZE];intsolution[MAXSIZE];intw[MAXSIZE][MAXSIZE];//weightintc[MAXSIZE][MAXSIZE];//costintminWeight;intcur_minWeight;voidBacktrack(intt,intn,intm,intd){if(t>n){if(cur_minWeight=0){Backtrack(t+1,n,m,d);}cur_minWeight-=w[t][i];//if(Constraint(t)&&Bound(t))Backtrack(t+1,n,m,d);d+=c[t][i];}}return;}intmain(){intn,m,d;cout<<"Pleaseinputtheinputfilepath:"<>strPath;ofstreamfout(strPath);if(fin.good()&&fout.good()){minWeight=INF;cur_minWeight=0;fin>>n>>m>>d;intj,k;for(j=1;j<=n;++j){for(k=1;k<=m;++k){fin>>c[j][k];}}for(j=1;j<=n;++j){for(k=1;k<=m;++k){fin>>w[j][k];}}Backtrack(1,n,m,d);fout<#include#include#includeusingnamespacestd;#defineMAX_NODE256typedefstruct_node{intweight,price;intlevel,th;struct_node*prev;}node;voidqs(int*a,int*s,intb,inte)//快速排序{intt,c=a[s[b]];intl=b,r=e;while(l=c)--r;t=s[r];s[r]=s[l];s[l]=t;while(lque;list::iteratorit;node*pnode;/*读取文件*/FILE*pf;if((pf=fopen("input.txt","r"))!=0){fscanf(pf,"%d%d%d",&n,&m,&c);w=(int*)malloc(n*m*sizeof(int));//重量p=(int*)malloc(n*m*sizeof(int));//价格for(i=0;i
记录
混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载
买了i个零件后，买完剩下的零件至少还要多少钱minprice[n]=0;//买了n个零件之后，不需要再买了for(i=0;i=0;--i)//计算买剩下的零件至少要多少钱{minprice[i]=minprice[i+1]+minprice[i];}for(i=0;iweight=w[s[0][i]];pnode->price=p[s[0][i]];if(pnode->price+minprice[2]<=c){pnode->th=i;pnode->level=1;pnode->prev=0;que.push_back(pnode);}elsedeletepnode;}while(!que.empty())//计算，直到得出结果或者队列为空{level=que.front()->level;price=que.front()->price;weight=que.front()->weight;if(levelweight=weight+w[level*m+s[level][i]];pnode->price=price+p[level*m+s[level][i]];if(pnode->price+minprice[level+1]<=c)//剪枝，如果当前结点剩下的钱不够买全所有零件，那么剪掉{pnode->th=s[level][i];pnode->level=level+1;pnode->prev=que.front();for(it=que.begin();it!=que.end();++it)//按重量递增构造优先队列if(pnode->weight<(*it)->weight)break;que.insert(it,pnode);if(level==n-1)break;//如果已经找到
答案
八年级地理上册填图题岩土工程勘察试题省略号的作用及举例应急救援安全知识车间5s试题及答案
，退出循环}elsedeletepnode;}que.pop_front();if(ilevel!=n){printf("cannotfindanswer!!");getchar(); exit(0);}pf=fopen("output.txt","w");if(pf){fprintf(pf,"%d\n",pnode->weight);intcount=n,ans[n];while(pnode){ans[--count]=pnode->th;pnode=pnode->prev;}for(i=0;i
本文档为【算法设计课程报告--最小重量机器设计问题】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。
[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
浙公网安备 33021202002483