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

《《算法设计》课程报告__最小重量机器设计问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、课程名称：学生姓名：学生学号：《算法设计》课程报告课题名称：算法设计课题负责人名（学号）：---同组成员名单（角色）：---指导教师：---评阅成绩：评阅意见：提交报告时间：2014年6月17日-10-课程名称：学生姓名：学生学号：最小重量机器设计问题计算机科学与技术专业学生--指导老师---[题目描述]设某一机器由n个部件组成，每一种部件都可以从m个不同的供应商处购得。高wij是从供应商j处购得的部件i的重量，cij是相应的价格。试设计一个算法，给出总价格不超过c的最小重量机器设计。编程任务：对于给定的机器部件重量和机器部件价格，

2、编程计算总价格不超过d的最小重量机器设计。数据输入：由文件input.txt给出输入数据。第一行有3个正整数n，m和d。接正业的2n行，每行n个数。前n行是c，后n行是w。结果输出：将计算出的最小重量，以及每个部件的供应商输出到文件output.txt。输入文件示例输出文件示例input.txtoutput.txt3344123131321222123321222-10-课程名称：学生姓名：学生学号：[算法分析]采用回溯算法和分支定界法分别实现，对于回溯法，采用深度优先搜索对子集树进行剪枝，剪枝条件是当前的总费用不超过总费用；对于分

3、支定界法，采用按照层次遍历对子集树进行剪枝，并将每层的结点按照重量由小到大进行排序，将相应下标保存在二维数组s中，以便构造最优解。两种算法是时间复杂度都是O(m^n)，空间复杂度均为O(nm)，但由于分支定界法在已经排好序的序列中查找，因此查找到的第一个解即为最优解，理论上来说，时间效率会比回溯法高。[程序实现]回溯法代码#include#include#include#include#include#includeusi

4、ngnamespacestd;#defineINF999999999#defineMAXSIZE100+1intcur_solution[MAXSIZE];intsolution[MAXSIZE];intw[MAXSIZE][MAXSIZE];//weightintc[MAXSIZE][MAXSIZE];//costintminWeight;intcur_minWeight;voidBacktrack(intt,intn,intm,intd){-10-课程名称：学生姓名：学生学号：if(t>n){if(cur_minWeight

5、inWeight){//保存最优解和最优值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

6、+1,n,m,d);d+=c[t][i];}}return;}intmain(){intn,m,d;cout<<"Pleaseinputtheinputfilepath:"<>strPath;ofstreamfout(strPath);if(fin.good

7、()&&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<

8、.close();fin.close();}else{cout<<"Openfileerror!"<