实验报告最小重量机器设计问题

《实验报告最小重量机器设计问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、Ah口课程名称：算法设计与分析实验项目：最小重量机器设计问题实验类型：综合性口设计性口验证性专业班别：姓名：学号：实验课室：第计算机实验室指导教师：实验日期：2013-12-12一、实验项目训练方案小组合作：是口否0I小组成员：实验目的：1.通过回溯法的示例程序理解回溯法的基木思想；2.运用回溯法解决实际题进一步加深对回溯法的理解和运用。实验场地及仪器、设备和材料操作系统：winXP、Win7、ubuntu开发环境：VC++6.0、VisualStudio2010实验训练内容（ti拈实验原理和操作步骤）：一、实

2、验内容：1.练习使用回溯法求解“最小重量机器设计”问题。二、实验题题目描述设某一机器巾n个部件组成，毎一种部件都可以从m个不同的供应商处购得。设wij是从供应商j处购得的部件i的重量，cij是相应的价格。设计一个优先队列式分支限界法，给出总价格不超过d的最小重量机器设计。对于给定的机器部件熏呈和机器部件价格，设计一个优先队列式分支限界法，计算总价格不超过d的最小重贷机器设计。输入输入数据的第1行有3个正整数n，0!和（1（n,m<20,d<100）。接下来的2n行，每行n个数。前n行是c，后n行是w。输出示例输

3、出4131将计算出的最小重兒:，以及每个部什的供应商分成两行输出。无解请输出“NoSolution!”。示例输入334123321222123321222三、实验步骤1.理解冋溯算法思想和算法示例；2.上机输入和调试算法示例程序；3.理解实验题的问题要求；4.上机输入和调试&己所编的实验题程序；5.验证并分析实验题的实验结果；6.整理出实验报告。代码如下：#includeusingnamespacestd;constintlen=30;constintmaxWeight=4000;intn，

4、m，cost;intw[len][len];//重量intc[len][len];//价钱intvisit

5、len

6、;intpathflen];intminWeight=maxWeight;voidfindMinWeight(intcurrent,intweight,inti)//当前策略的价钱和最小重量{if(i>=n){minWeight=weight;for(intj=0;j

7、fj]<=cost&&weight+w[i][j]

8、

9、j

10、;weight-=w[i][j];}}}intmain(){while(cin»n»m»cost){minWeight=maxWeight;inti，j;for(i=0;i<2*n;i++){for(j=0;j

11、

12、i

13、

14、j

15、;elsecin»w[i-n][j];}}findMinWeight(O,O,O);if(minWeight==maxWeight)cout<<"-1"«endl;elsecout«minWeight«endl;for(i=0;i

16、成绩评定:指导教师签名：