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

算法设计课程报告课题名称：算法设计课题负责人名（学号） ：-同组成员名单（角色） ：-指导教师：-评阅成绩：评阅意见：提交报告时间：2014 年 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.txt3 3 441 2 31 3 13 2 12 2 21 2 33 2 12 2 2-1-课程名称：学生姓名：学生学号： 算法分析采用回溯算法和分支定界法分别实现，对于回溯法，采用深度优先搜索对子集树进行剪枝，剪枝条件是当前的总费用不超过总费用；对于分支定界法，采用按照层次遍历对子集树进行剪枝，并将每层的结点按照重量由小到大进行排序，将相应下标保存在二维数组s 中，以便构造最优解。两种算法是时间复杂度都是O(mn) ，空间复杂度均为O(nm) ，但由于分支定界法在已经排好序的序列中查找，因此查找到的第一个解即为最优解，理论上来说，时间效率会比回溯法高。 程序实现回溯法代码#include #include #include #include #include #include using namespace std;#define INF 999999999#define MAXSIZE 100+1int cur_solutionMAXSIZE;int solutionMAXSIZE;int wMAXSIZEMAXSIZE; /weightint cMAXSIZEMAXSIZE; /costint minWeight;int cur_minWeight;void Backtrack(int t,int n,int m,int d)-2-课程名称：学生姓名：学生学号：if(tn)if(cur_minWeight minWeight)/ 保存最优解和最优值 minWeight = cur_minWeight;for(int r=1;r=n;+r)solutionr = cur_solutionr;elsefor(int i=1;i=0) Backtrack(t+1,n,m,d);cur_minWeight -= wti;/if(Constraint(t) & Bound(t) Backtrack(t+1,n,m,d); d += cti;return;int main()int n,m,d;coutPlease input the input :endl;char strPath63;while(scanf(%s,strPath)=1)ifstream fin(strPath);-3-课程名称：学生姓名：学生学号：coutPlease input the output :strPath;ofstream fout(strPath);if(fin.good() & fout.good()minWeight = INF;cur_minWeight = 0;finnmd;int j,k;for(j=1;j=n;+j)for(k=1;kcjk;for(j=1;j=n;+j)for(k=1;kwjk;Backtrack(1,n,m,d);foutminWeightendl;for(int r=1;r=n;+r)foutsolutionr ;foutendl;fout.close();fin.close();elsecoutOpen !endl;exit(0);-4-课程名称：学生姓名：学生学号：coutendlendlPlease input the input :endl;return 0;分支定界法代码#include #include #include #include using namespace std;#define MAX_NODE 256typedef struct _nodeint weight,price;int level,th;struct _node *prev;node;void qs(int *a,int *s,int b,int e)/快速排序int t,c=asb;int l=b,r=e;while(lr)while(l=c)-r;t=sr;sr=sl;sl=t;while(lr&aslc)+l;t=sr;sr=sl;sl=t;if(bl)qs(a,s,b,l-1);-5-课程名称：学生姓名：学生学号：if(le)qs(a,s,l+1,e);int main()int *w=0,*p=0,n,m,c,i,j;int *minprice;int level,price,weight;list que;list:iterator it;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);elseprintf(no input file!n);getchar();exit(0);-6-课程名称：学生姓名：学生学号：/*准备数据*/int snm;/ 用来为每一种零件的质量排序，for(i=0;in;+i)for(j=0;jm;+j)sij=j;minprice=(int*)malloc(n+1)*sizeof(int);/用来记录买了i个零件后，买完剩下的零件至少还要多少钱minpricen=0;/ 买了 n 个零件之后，不需要再买了for(i=0;in;+i)minpricei=pi*m;for(j=1;jm;+j)/ 找出买第i 个零件的最低价格minpricei=minpricei=0;-i)/ 计算买剩下的零件至少要多少钱minpricei=minpricei+1+minpricei;for(i=0;in;+i)/ 每种零件按重量排序，排序下标记录的s 中 ,排序后wi*m+sij， i 相同时，对于变量j 是递增的qs(w+i*m,si,0,m-1);/*开始计算*/for(i=0;iweight=ws0i;-7-课程名称：学生姓名：学生学号：pnode-price=ps0i;if(pnode-price+minprice2th=i;pnode-level=1;pnode-prev =0;que.push_back(pnode);else delete pnode;while(!que.empty()/ 计算，直到得出结果或者队列为空level =que.front()-level;price =que.front()-price;weight=que.front()-weight;if(leveln)for(i=0;iweight=weight+wlevel*m+sleveli;pnode-price=price+plevel*m+sleveli;if(pnode-price+minpricelevel+1th=sleveli;pnode-level=level+1;pnode-prev =que.front();for(it=que.begin();it!=que.end();+it)/按 重 量 递增构造优先队列if(pnode-weightweight)-8-课程名称：学生姓名：学生学号：break;que.insert(it,pnode);if(level=n-1)break;/ 如果已经找到答案，退出循环else delete pnode;que.pop_front();if(ilevel!=n)printf(can not find answer!);getchar();exit(0);pf=fopen(output.txt,w);if(pf)fprintf(pf,%dn,pnode-weight);int count=n,ansn;while(pnode)ans-count=pnode-th;pnode=pnode-prev;for(i=0;in;+i)fprintf(pf,%d ,ansi);fputc(n,pf);-9-课程名称：学生姓名：学生学号：fclose(pf);if(minprice)free(minprice);if(w)free(w);if(p)free(p);return 0; 运行结果回溯法运行结果如下，分支定界法结果与下列一致，读者可以自行运行比对参考文献1王晓东 . 计算机算法设计与分析.-3版 .-北京：电子工业出版社2007.5-10-