实验五--箱子装载问题(分支限界法)(共5页).doc

《实验五--箱子装载问题(分支限界法)(共5页).doc》由会员分享，可在线阅读，更多相关《实验五--箱子装载问题(分支限界法)(共5页).doc（5页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

2、系列的选择来得到问题的解。他所做的每一个选择都是当前状态下局部最好选择，即贪心选择。四、 程序代码：贪心算法：#include#include#define N 100using namespace std;int main()int tN,w0N,wN,n,c,m,i,j;int max=0,weight=0;bool txN;cout请输入轮船的载重量c：c;cout请输入可以装入的集装箱的数目n：n;cout请输入各集装箱的重量wi(1=i=n)：endl;for(int i=0;iw0i;wi+1=w0i;txi+1=false;for(i=1;in;i+)for(j=i+1;jwj)

3、 int tem;tem=wj;wj=wi;wi=tem;for(i=1;i=n;i+)printf(%d,wi);printf(n);for(i=1;i=n;i+)int min=weight+wi;if(min=c)weight+=wi;txi=true;m=i-1;cout最优装载情况为：endl;cout装入轮船的集装箱为：;max=0;for(i=1;i=m;i+)if(txi)max+=wi;coutwi-;coutendl;cout装入的集装箱的最大重量为：maxendl;system(pause);回溯法：#includeusing namespace std;class Lo

4、adingfriend float MaxLoading(float,float,int);public:void Backtrack(int i);int n;int *x,*bestx;float *w,c,cw,bestw,r;float Maxloading(float w1,float c1,float c2,int n1,int bestx1)Loading k;int j;float MAXLoad;k.x= new int n1+1;k.bestx=bestx1;k.w = w1;k.c = c1;k.n = n1;k.cw = 0;k.bestw = 0;k.r = 0;fo

5、r(int i=1;i=n1;i+)k.r+=w1i;k.Backtrack(1);delete k.x;cout船1最优装载：k.bestwendl;MAXLoad=k.bestw;for( j=1;j=n1;j+)if(k.bestxj=0)MAXLoad+=w1j;c2-=w1j;if(c20)cout找不到合理装载方案！endl;return -1;cout船1中的箱子：;for( j=1;j=n1;j+)if(k.bestxj=1)coutj ;coutendl;cout船2中的箱子：;for( j=1;j=n1;j+)if(k.bestxj=0)coutj;coutn)if(cwb

6、estw)for(int j=1;j=n;j+)bestxj=xj;bestw = cw;return;r-=wi;if(cw+wibestw)xi = 0;Backtrack(i+1);r+=wi;int main()float w20;float c1,c2,k;int n,bestx20;coutn;cout输入箱子重量：;for(int i=1;iwi;coutc1c2;k=Maxloading(w,c1,c2,n,bestx);if(k!=-1)cout总体最优装载：kendl;return 1;五、 结果运行与分析：贪心算法：回溯法：六、心得与体会： 通过本次实验，自己再次的联系了贪心算法和回溯法的应用，本次实验自己测试了很多次才成功，收获蛮大的，自己的编程能力进一步的提高了。专心-专注-专业