实验九装载问题

《实验九装载问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法设计与分析实验报告姓名：杨勇涛班级：计科102一、实验名称：装载问题二、时间：2012年4月18日，星期三，第四节地点：12#311二、实验目的及要求有n个集装箱要装上2艘载重量分别为c1和c2的轮船，其中第i个集装箱的重量为wi，要求确定是否有一个合理的装载方案可将这个集装箱装上这2艘轮船。如果有，找出一种装载方案。注意，在满足的条件下才可能将这个集装箱装上这2艘轮船。三、实验环境Vc++四、实验内容在键盘上输入集装箱的个数、轮船的载重量、每个集装箱的重量。五、算法描述及实验步骤1.首先将第一手轮船尽可能装满；2.然后将剩余的集装箱装上第二艘轮船。将第一艘轮船尽可能装满等价

2、于选区全体集装箱的一个子集，使该子集中集装箱重量之和最接近c1.由此可知，装载问题等价于以下特殊的0-1背包问题。六、调试过程及实验结果七、总结回溯的一般步骤：1.针对所给问题，定义问题的解空间；2．确定一语搜索的解空间结构；3.以深度优先方式索解空间，并在搜索过程中用剪枝函数避免无效搜索。八、附录（源程序清单）#include#include#includetypedefintStatus;typedefintType;intn=0;Type*x=(Type*)malloc((50)*sizeof(Type));Ty

3、pe*bestx=(Type*)malloc((50)*sizeof(Type));Typec=0,cw=0,bestw=0,r=0,*w=(Type*)malloc((50)*sizeof(Type));intBacktrack(inti){intj_index;if(i>n){if(cw>bestw){for(j_index=1;j_index<=n;j_index++)bestx[j_index]=x[j_index];bestw=cw;}return1;}r-=w[i];if(cw+w[i]<=c){x[i]=1;cw+=w[i];Backtrack(i+1);cw-=w

4、[i];}if(cw+r>bestw){x[i]=0;Backtrack(i+1);}r+=w[i];}Type*Initiate(){intindex=1;printf("输入集装箱个数：");scanf("%dd",&n);printf("输入轮船在重量：");scanf("%d",&c);while(index<=n){printf("输入集装箱%d的重量：",index);scanf("%d",&w[index]);index++;}bestw=0;cw=0;r=0;for(index=1;index<=n;index++)r+=w[index];printf("n=%d

5、c=%dcw=%dbesrw=%dr=%d",n,c,cw,bestw,r);for(index=1;index<=n;index++){printf("w[%d]=%d",index,w[index]);}printf("");returnw;}intmain(){inti;Initiate();Backtrack(1);for(i=1;i<=n;i++){printf("%d",w[i]);printf("%d",bestx[i]);}returnbestw;}