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

《算法设计》课程报告课题名称:算法设计课题负责人名(学号):---同组成员名单(角色):---指导教师:---评阅成绩:评阅意见:提交报告时间: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;#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;();();}else{cout<<Openfileerror!<<endl;exit(0);}cout<<endl<<endl<<Pleaseinputtheinputfilepath:<<endl;}return0;}分支定界法代码#include<>#include<>#include<list>#include<iostream>usingnamespacestd;#defineMAX_NODE25