实验十-回溯法

宁夏师范学院数学与计算机科学学院《算法分析与设计》实验报告实验序号：10实验项目名称：回溯法学号201004230123姓名专业、班10信科班实验地点318指导教师惠云时间14:44一、实验目的及要求（1）掌握回溯法的基本思想；（2）掌握使用回溯法解决实际问题的基本方法和步骤；二、实验设备（环境）及要求1、环境要求：硬件：PC（PII以上，128M以上内存）、因特网接入；软件：WindowsXP操作系统、VC++6.0编程环境。2、实验要求：(1)独立完成实验，源代码书写规范；(2)程序运行结果以屏幕截图的方式粘贴在对应位置，截图必须清晰准确；(3)实验完成后必须有实验结果的分析及本次实验的总结。三、实验内容与步骤1、设计求解装载问题的程序，并将装入轮船的最优装载重量及装载序列在屏幕上显示。实验代码：#includestdio.h#includestdlib.hintc1,c2,n;int*w,*bestx,*x;intremain;intbestw;intcw;voidLoad(inti){intk;if(in){for(k=1;k=n;k++){bestx[k]=x[k];}bestw=cw;return;}remain-=w[i];if(cw+w[i]=c1){x[i]=1;cw+=w[i];Load(i+1);cw-=w[i];}if(remain+cwbestw){x[i]=0;Load(i+1);}remain-=w[i];}intBestAnswer(){inti;remain=0;bestx=(int*)malloc(sizeof(int)*(n+1));x=(int*)malloc(sizeof(int)*(n+1));for(i=1;i=n;i++){remain+=w[i];x[i]=0;}bestw=0;Load(1);returnbestw;}intmain(){while(1){inti,r=0;scanf(%d%d%d,&c1,&c2,&n);if(n==0)break;w=(int*)malloc(sizeof(int)*(n+1));for(i=1;i=n;i++){scanf(%d,&w[i]);}bestw=BestAnswer();for(i=1;i=n;i++){if(bestx[i]!=1)r+=w[i];}if(c2=r)printf(yes\n);elseprintf(no\n);}}四、实验结果与数据处理五、分析与讨论1、分析求解装载问题算法的时间复杂度。六、教师评语签名：日期：年月日成绩