《算法设计》课程报告--最小重量机器设计问题

《算法设计》课程报告课题名称：算法设计课题负责人名（学号）：---同组成员名单（角色）：---指导教师：---评阅成绩：评阅意见：提交报告时间：2014年6月17日课程名称：学生姓名：学生学号：-1-最小重量机器设计问题计算机科学与技术专业学生--指导老师---[题目描述]设某一机器由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课程名称：学生姓名：学生学号：-2-[算法分析]采用回溯算法和分支定界法分别实现，对于回溯法，采用深度优先搜索对子集树进行剪枝，剪枝条件是当前的总费用不超过总费用；对于分支定界法，采用按照层次遍历对子集树进行剪枝，并将每层的结点按照重量由小到大进行排序，将相应下标保存在二维数组s中，以便构造最优解。两种算法是时间复杂度都是O(m^n)，空间复杂度均为O(nm)，但由于分支定界法在已经排好序的序列中查找，因此查找到的第一个解即为最优解，理论上来说，时间效率会比回溯法高。[程序实现]回溯法代码#includeiostream#includestdlib.h#includefstream#includevector#includestdio.h#includestring.husingnamespacestd;#defineINF999999999#defineMAXSIZE100+1intcur_solution[MAXSIZE];intsolution[MAXSIZE];intw[MAXSIZE][MAXSIZE];//weightintc[MAXSIZE][MAXSIZE];//costintminWeight;intcur_minWeight;voidBacktrack(intt,intn,intm,intd){课程名称：学生姓名：学生学号：-3-if(tn){if(cur_minWeightminWeight){//保存最优解和最优值minWeight=cur_minWeight;for(intr=1;r=n;++r){solution[r]=cur_solution[r];}}}else{for(inti=1;i=m;++i){d-=c[t][i];cur_solution[t]=i;cur_minWeight+=w[t][i];if(d=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;coutPleaseinputtheinput:endl;charstrPath[63];while(scanf(%s,strPath)==1){ifstreamfin(strPath);课程名称：学生姓名：学生学号：-4-coutPleaseinputtheoutput:endl;cinstrPath;ofstreamfout(strPath);if(fin.good()&&fout.good()){minWeight=INF;cur_minWeight=0;finnmd;intj,k;for(j=1;j=n;++j){for(k=1;k=m;++k){finc[j][k];}}for(j=1;j=n;++j){for(k=1;k=m;++k){finw[j][k];}}Backtrack(1,n,m,d);foutminWeightendl;for(intr=1;r=n;++r){foutsolution[r];}foutendl;fout.close();fin.close();}else{coutOpen!endl;exit(0);课程名称：学生姓名：学生学号：-5-}coutendlendlPleaseinputtheinput:endl;}return0;}分支定界法代码#includestdio.h#includestdlib.h#includelist#includeiostreamusingnamespacestd;#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(lr){while(lr&&a[s[r]]=c)--r;t=s[r];s[r]=s[l];s[l]=t;while(lr&&a[s[l]]c)++l;t=s[r];s[r]=s[l];s[l]=t;}if(bl)qs(a,s,b,l-1);课程名称：学生姓名：学生学号：-6-if(le)qs(a,s,l+1,e);}intmain(){int*w=0,*p=0,n,m,c,i,j;int*minprice;intlevel,price,weight;listnode*que;listnode*::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;in;++i)for(j=0;jm;++j)fscanf(pf,%d,w+i*m+j);for(i=0;in;++i)for(j=0;jm;++j)fscanf(pf,%d,p+i*m+j);fclose(pf);}else{printf(noinputfile!!\n);getchar();exit(0);课程名称：学生姓名：学生学号：-7-}/*准备数据*/ints[n][m];//用来为每一种零件的质量排序，for(i=0;in;++i)for(j=0;jm;++j)s[i][j]=j;minprice=(int*)malloc((n+1)*sizeof(int));//用来记录买了i个零件后，买完剩下的零件至少还要多少钱minprice[n]=0;//买了n个零件之后，不需要再买了for(i=0;in;++i){minprice[i]=p[i*m];for(j=1;jm;++j)//找出买第i个零件的最低价格{minprice[i]=minprice[i]p[i*m+j]?minprice[i]:p[i*m+j];}}for(i=n-2;i=0;--i)//计算买剩下的零件至少要多少钱{minprice[i]=minprice[i+1]+minprice[i];}for(i=0;in;++i)//每种零件按重量排序，排序下标记录的s中,排序后w[i*m+s[i][j]]，i相同时，对于变量j是递增的qs(w+i*m,s[i],0,m-1);/*开始计算*/for(i=0;im;++i)//初始数据把第一种零件的所有情况放入活结点队列{pnode=newnode;pnode-weight=w[s[0][i]];课程名称：学生姓名：学生学号：-8-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(leveln)for(i=0;im;++i)//如果队首不为叶子结点，扩展队首结点{pnode=newnode;pnode-weight=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)课程名称：学生姓名：学生学号：-9-break;que.insert(it,pnode);if(level==n-1)break;//如果已经找到答案，退出循环}elsedeletepnode;}que.pop_front();if(im)break;//如果已经找到答案，退出循环}/*输出答案*/if(pnode-level!=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;in;++i)fprintf(pf,%d,ans[i]);fputc('\n',pf);课程名称：学生姓名：学生学号：-10-fclose(pf);}if(minprice)free(minprice);if(w)free(w);if(p)free(p);return0;}[运行结果]回溯法运行结果如下，分支定界法结果与下列一致，读者可以自行运行比对参考文献[1]王晓东.计算机算法设计与分析.--3版.--北京：电子工业出版社2007.5