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

实验报告课程名称：算法设计与分析实验项目：最小重量机器设计问题实验类型：综合性□设计性□验证性专业班别：姓名：学号：实验课室：第计算机实验室指导教师：实验日期：2013-12-12一、实验项目训练方案小组合作：是□否小组成员：实验目的：1.通过回溯法的示例程序理解回溯法的基本思想；2.运用回溯法解决实际问题进一步加深对回溯法的理解和运用。实验场地及仪器、设备和材料操作系统：winXP、Win7、ubuntu开发环境：VC++6.0、VisualStudio2010实验训练内容（包括实验原理和操作步骤）：一、实验内容：1.练习使用回溯法求解“最小重量机器设计”问题。二、实验题题目描述设某一机器由n个部件组成，每一种部件都可以从m个不同的供应商处购得。设wij是从供应商j处购得的部件i的重量，cij是相应的价格。设计一个优先队列式分支限界法，给出总价格不超过d的最小重量机器设计。对于给定的机器部件重量和机器部件价格，设计一个优先队列式分支限界法，计算总价格不超过d的最小重量机器设计。输入输入数据的第1行有3个正整数n，m和d（n，m20，d100）。接下来的2n行，每行n个数。前n行是c，后n行是w。输出将计算出的最小重量，以及每个部件的供应商分成两行输出。无解请输出“NoSolution!”。示例输入334123321222123321222示例输出4131三、实验步骤1．理解回溯算法思想和算法示例；2．上机输入和调试算法示例程序；3．理解实验题的问题要求；4．上机输入和调试自己所编的实验题程序；5．验证并分析实验题的实验结果；6．整理出实验报告。代码如下：#includeiostreamusingnamespacestd;constintlen=30;constintmaxWeight=4000;intn,m,cost;intw[len][len];//重量intc[len][len];//价钱intvisit[len];intpath[len];intminWeight=maxWeight;voidfindMinWeight(intcurrent,intweight,inti)//当前策略的价钱和最小重量{if(i=n){minWeight=weight;for(intj=0;jn;j++)path[j]=visit[j];return;}for(intj=0;jm;j++){if(current+c[i][j]=cost&&weight+w[i][j]minWeight){current+=c[i][j];weight+=w[i][j];visit[i]=j+1;findMinWeight(current,weight,i+1);current-=c[i][j];weight-=w[i][j];}}}intmain(){while(cinnmcost){minWeight=maxWeight;inti,j;for(i=0;i2*n;i++){for(j=0;jm;j++){if(in)cinc[i][j];elsecinw[i-n][j];}}findMinWeight(0,0,0);if(minWeight==maxWeight)cout-1endl;else{coutminWeightendl;for(i=0;in;i++){if(i==0)coutpath[i];elsecoutpath[i];}coutendl;}}return0;}结果：二、实验总结与评价实验总结（包括实验数据分析、实验结果、实验过程中出现的问题及解决方法等）：对实验的自我评价：指导教师评语：学生实验成绩评定：指导教师签名：日期：年月日