




已阅读5页,还剩6页未读, 继续免费阅读
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
算法设计课程报告课题名称: 算法设计 课题负责人名(学号): - 同组成员名单(角色): -指导教师: -评阅成绩: 评阅意见: 提交报告时间: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.txt output.txt3 3 4 41 2 3 1 3 13 2 12 2 21 2 33 2 12 2 2算法分析采用回溯算法和分支定界法分别实现,对于回溯法,采用深度优先搜索对子集树进行剪枝,剪枝条件是当前的总费用不超过总费用;对于分支定界法,采用按照层次遍历对子集树进行剪枝,并将每层的结点按照重量由小到大进行排序,将相应下标保存在二维数组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)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 file path:endl;char strPath63;while(scanf(%s,strPath)=1)ifstream fin(strPath);coutPlease input the output file path: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 file error!endl;exit(0);coutendlendlPlease input the input file path: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); 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);/* 准备数据 */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;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)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
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 智能制造背景下15寸彩色监视器生产良品率提升与自动化瓶颈的博弈分析
- 智能传感技术如何重构传统液压单元故障诊断体系
- 新能源汽车电池热失控预警与电源主动保护闭环
- 新能源割引机动力电池热失控防护与作业效率的博弈平衡
- 新型环保胶辊材料在复合工艺中的界面结合强度与耐化学腐蚀测试
- 新型复合涂层技术对转化管氢致应力腐蚀开裂的抑制机理
- 新型光响应性2-乙酰基吡咯衍生物在智能药物递送系统中的应用瓶颈
- 数据中心能效比优化视角下的外壳拓扑设计与能源回收机制
- 数字孪生技术在连接器预研阶段多物理场仿真验证价值
- 散装碳粉数字化供应链中数据安全与成本控制冲突
- 焦虑症的课件
- 2025安徽宣城市总工会招聘社会化工会工作者13人笔试参考题库附答案解析
- 北京数语科技Datablau数据模型与数据资产平台介绍
- 2025年招聘面试技巧指南面试官角度下的面试题预测与应对策略
- 人体对外界环境的感知+课件-2025-2026学年人教版生物八年级上册
- 无人机驾驶培训专业知识课件
- 新型集体经济课件
- 临床护理师资培训体系构建
- 轨道列车司机四级题库及答案
- 生物标志物应用-洞察及研究
- 胫腓骨骨折教学查房课件
评论
0/150
提交评论