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

NurfürdenpersönlichenfürStudien,Forschung,zukommerziellenZweckenverwendetwerdenNurfürdenpersönlichenfürStudien,Forschung,zukommerziellenZweckenverwendetwerden《算法设计》课程报告课题名称:算法设计课题负责人名(学号):---同组成员名单(角色):--- 指导教师:--- 评阅成绩: 评阅意见: 提交报告时间:2014年6月17日最小重量机器设计问题计算机科学与技术专业学生--指导老师---[题目描述]设某一机器由n个部件组成,每一种部件都可以从m个不同的供应商处购得。高wij是从供应商j处购得的部件i的重量,cij是相应的价格。试设计一个算法,给出总价格不超过c的最小重量机器设计。编程任务:对于给定的机器部件重量和机器部件价格,编程计算总价格不超过d的最小重量机器设计。数据输入:。第一行有3个正整数n,m和d。接正业的2n行,每行n个数。前n行是c,后n行是w。结果输出:将计算出的最小重量,。[算法分析]采用回溯算法和分支定界法分别实现,对于回溯法,采用深度优先搜索对子集树进行剪枝,剪枝条件是当前的总费用不超过总费用;对于分支定界法,采用按照层次遍历对子集树进行剪枝,并将每层的结点按照重量由小到大进行排序,将相应下标保存在二维数组s中,以便构造最优解。两种算法是时间复杂度都是O(m^n),空间复杂度均为O(nm),但由于分支定界法在已经排好序的序列中查找,因此查找到的第一个解即为最优解,理论上来说,时间效率会比回溯法高。[程序实现]回溯法代码#include<iostream>#include<>#include<fstream>#include<vector>#include<>#include<>usingnamespacestd;#defineINF9#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<minWeight){//保存最优解和最优值 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; cout<<"Pleaseinputtheinputfilepath:"<<endl; charstrPath[63]; while(scanf("%s",strPath)==1){ ifstreamfin(strPath); cout<<"Pleaseinputtheoutputfilepath:"<<endl; cin>>strPath; ofstreamfout(strPath); if(()&&()){ 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<<minWeight<<endl; for(intr=1;r<=n;++r){ fout<<solution[r]<<""; } fout<<endl;