实验十-回溯法.doc

《实验十-回溯法.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、宁夏师范学院数学与计算机科学学院《算法分析与设计》实验报告实验序号：10　　实验项目名称：回溯法学　　号3姓　　名专业、班10信科班实验地点318指导教师惠云时间14:44一、实验目的及要求（1）掌握回溯法的基本思想；（2）掌握使用回溯法解决实际问题的基本方法和步骤；二、实验设备（环境）及要求1、环境要求：硬件：PC（PII以上，128M以上内存）、因特网接入；软件：WindowsXP操作系统、VC++6.0编程环境。2、实验要求：(1)独立完成实验，源代码书写规范；(2)程序运行结果以屏幕截图的方式粘贴

2、在对应位置，截图必须清晰准确；(3)实验完成后必须有实验结果的分析及本次实验的总结。三、实验内容与步骤1、设计求解装载问题的程序，并将装入轮船的最优装载重量及装载序列在屏幕上显示。实验代码：#include"stdio.h"#include"stdlib.h"intc1,c2,n;int*w,*bestx,*x;intremain;intbestw;intcw;voidLoad(inti){intk;if(i>n){for(k=1;k<=n;k++){bestx[k]=x[k];}bestw=cw;ret

3、urn;}remain-=w[i];if(cw+w[i]<=c1){x[i]=1;cw+=w[i];Load(i+1);cw-=w[i];}if(remain+cw>bestw){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];

4、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("

5、yes");elseprintf("no");}}四、实验结果与数据处理五、分析与讨论1、分析求解装载问题算法的时间复杂度。六、教师评语签名：日期：年月日成绩