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

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