箱子装载问题.doc

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

1、实验五箱子装载问题一、实验目的1、理解和复习所学各种算法的概念；2、掌握和复习所学各种算法的基本要素；3、掌握各种算法的优点和区别；4、通过应用范例掌握选择最佳算法的设计技巧与策略；二、实验内容及要求1、使用贪心算法、回溯法、分支限界法解决箱子装载问题。（任选两种）2、通过上机实验进行算法实现。3、保存和打印出程序的运行结果，并结合程序进行分析，上交实验报告。三、实验原理回溯法原理：从开始结点出发，以深度优先方式搜索整个解空间。这个节点成为活结点，同时也成为当前的扩展节点。在当前的扩展节点处，搜索向纵深方向一致

2、一个新节点。贪心算法原理：贪心算法通过一系列的选择来得到问题的解。他所做的每一个选择都是当前状态下局部最好选择，即贪心选择。四、程序代码（1）贪心算法#include#includevoidswap(int&x,int&y){//交换intt;t=x;x=y;y=t;}voidsort(intw[],intt[],intn)//排序，有小到大{for(intm=0;m

3、n-1;while(i>0){lastExchangeIndex=0;for(j=0;j

4、&&w[t[j]]<=c;j++){x[t[j]]=1;c-=w[t[j]];//装入}}intmian(){intn,c;printf("请输入物品个数：");scanf("%d",&n);printf("请输入最大容量：");scanf("%d",&c);intx[200];//存储物品编号intw[200];//存储每个物品重量for(inti=0;i

5、r(intj=0;j#include#definenum100intbestx[num]={0};//存放最优解intw[num];//集装箱重量intx[num];//解intbestw=0;//最优装船重量

6、intcw=0;//当前已装船重量intn;//集装箱个数intc1;//第一船的重量intc2;//第二船的重量//限界函数intbound(intt)//选择当前节点又分支的剩余集装箱重之和{intrw=0;for(inti=t+1;tn)//到底叶子节点，求得一个可行解{if(cw>bestw){//当前解比以前解更优bestw=cw;for(i=1;i<=n

7、;i++)bestx[i]=x[i];};return;}else{if(cw+w[t]bestw)//右分支满足限界条件loadingRec(t+1);}}intmain(){n=4;//集装箱个数w[1]=4,w[2]=5,w[3]=3,w[4]=2;//集装箱重量c1=8;//第一个船重量c

8、2=7;//第二个船重量cw=0;bestw=0;loadingRec(1);//从第一个集装箱开始装箱printf("第一船的最优装载量为：%d",bestw);printf("第一船的最优解为");for(inti=1;i<=n;i++)printf("%d",bestx[i]);//求剩余集装箱的重量intcw2=0;for(inti=0;i<=n;i++)if(bestx[