版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、 最小重量机器设计问题1. 问题描述 设某一机器由n个部件组成,每一个部件都可以从m个不同的 供应商处购得。设wij是从供应商j处购得的部件i的重量,cij 是相应的价格。试设计一个算法,给出总价格不超过c的最小重 量机器设计。 算法设计:对于给定的机器部件重量和机器部件价格,计算总价 格不超过d的最小重量机器设计。算法流程分析 设开始时bestx=-1,-1,-1则相应的排列树由x0:n-1 的所有排列构成。 找最小重量机器设计的回溯算法Backtrack是类machine的公 有成员。私有数据成员整型数组Savex保存搜索过的路径,到达 叶节点后将数据赋值给数组bestx。成员bestw记
2、录当前最小重 量,cc表示当前花费,cw表示当前的重量。 在递归函数Backtrack中,在保证总花费不超过c的情况下: 当i=n时,当前扩展结点是排列树的叶节点。此时搜索到一个解, 判断此时的最小重量是否小于当前最小重量,若小于则更新bestw, 并得到搜索路径bestx。 当in时,当前扩展结点位于排列树的第i-1层。当x0:i 的花费小于给定最小花费时,算法进入排列树的第i层,否则将减 去相应的子树。算法用变量cc记录当前路径x0:i的费用。3. 算法正确性证明通过几组实例证明合法的输入可以得到正确的输出。实例见附录第2部分。算法复杂度分析 时间复杂度是 O(n2)5.参考文献1 王晓东
3、编著,计算机算法设计与分析(第4版)。北京:电子工业出版社,2012.26.附录(1)可执行代码如下:#includeusing namespace std;#define N 50class MinWmechineint n; /部件个数int m; /供应商个数int COST; /题目中的Cint cw; /当前的重量int cc; /当前花费int bestw; /当前最小重量int bestxN;int savexN;int wNN;int cNN;public:MinWmechine();void machine_plan(int i);void prinout();MinWmec
4、hine:MinWmechine() cw=0; /当前的重量cc=0; /当前花费bestw=-1; /当前最小重量bestxN;savexN;coutn;coutm;coutCOST;for(int j=0;jm;j+) for(int i=0;in;i+) cout请输入第 j+1 个供应商的第 i+1wij; cout请输入第 j+1 个供应商的第 i+1cij; if(wij0 | cij0) cout=n) if(cw bestw | bestw=-1) bestw=cw; for(int j=0;jn; j+) /把当前搜过的路径记下来 savexj=bestxj; return
5、;for(int j=0; jm; j+) /依次递归尝试每个供应商 if(cc+cijCOST) cc+=cij; cw+=wij; bestxi=j; machine_plan(i+1); bestxi=-1; cc-=cij; cw-=wij; void MinWmechine:prinout()int i,j,ccc=0;for(j=0;jm;j+) for(i=0;in;i+) cout第 j+1 供应商的第 i+1 部件重量:wij价格:cijn; for(j=0; jn; j+) bestxj=-1; machine_plan(0);coutn最小重量机器的重量是: bestwendl;for(int k=0; kn; k+) cout 第 k+1 部件来自供应商 savexk+1n; ccc+=cksavexk;coutn该机器的总
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 绿化养护方案(投标方案)
- 财务审计投标方案技术方案(技术方案)
- 2024年重庆市消防设施操作员《中级技能-维保方向》科目真题冲刺卷上半年B卷
- 2020年部编版小学语文六年级下册教案(全册)
- “八一建军节”庆祝活动主持词开场白和结束语范文
- 中药乌梢蛇课件
- 经皮肾镜碎石取石术的手术配合及细节护理
- 记账实操-塑胶水管店的账务处理分录
- 《中秋食月饼》幼儿园小学少儿美术教育绘画课件创意教程教案
- 2024年口服美容行业市场前景及投资研究报告
- 《支气管镜检查》课件
- 幼儿园中班散文《十月里的第一天》
- 慢性鼻窦炎诊疗指南及药物应用指南
- 申请研究院可行性方案
- 《绝缘电阻试验》课件
- 2024年国家通用技术康养公司招聘笔试参考题库含答案解析
- NB-T 47013.1-2015 承压设备无损检测 第1部分-通用要求
- 中小学人工智能教育的国内外研究综述
- 国有企业有限公司机构设置“三定”方案
- 产业园区招商引资应急预案和处理措施
- 寺庙开发运营项目投资计划书
评论
0/150
提交评论