实验五箱子装载问题

《实验五箱子装载问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

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

2、为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向一致一个新结点。四、程序代码：1、贪心算法：^include^include^include〈algorithm〉usingnamespacestd;constintmaxn=1000;intw[maxn];intx[maxn];intmain(){intn,c;pHntf("输入集装箱数量和轮船载重量：");while(〜scanf(〃％d%d〃，&n，&c)){printf("输入集装箱的重量：")；memset(x,0,sizeof(x));for(inti=0;i

3、anf("%d"，&'v[i]);sort(w,w+n);intans二0;for(inti=0;i〈n;i++)if(ans+w[i]<=c){ans+=w[i];x[i]=l;}printfC最大装载为％d",ans);printfr选中的集装箱重量分别为：z/);for(inti=0;i〈n;i++)if(x[i])printf(〃％d〃，w[i])}2、回溯法#includeusingnamespacestd;classLoadingfriendfloatMaxLoading(float[]，float，int);public:voidB

4、acktrack(inti);intn;int*bestx;float氺w，c，cw，bestw，r;};floatMaxloading(floatwl[],floatcl,floatc2,intnl，intbestxl[]){Loadingk;intj;floatMAXLoad;k.x=newint[nl+1];k.bestx=bestxl;k.w=wl;k.c=cl;k.n=nl;k.cw=0;k.bestw=0;k.r=0;for(inti=l;i<=nl;i++)k.r+=wl[i];k.Backtrack(1);delete[]k.x;cout〈<〃船1最优装载：

5、〃<〈k.bestw«endl:MAXLoad=k.bestw;for(j=l;j<=nl;j++)if(k.bestx[j]二=0)MAXLoad+=wl[j];c2-='vl[j];if(c2〈0){COut<〈"找不到合理装载方法"<

6、AXLoad;}voidLoading::Backtrack(inti){if(i〉n){if(cw>bestw){for(intj=l;j<=n;j++)bestx[j]=x[j];bestw二cw;}return;r-=w[i];if(cw+w[i]<=c){x[i]=l;cw+=w[i];Backtrack(i+1);cw~=w[i];}if(cw+r〉bestw){x[i]=0;Backtrack(i+1);}r+=w[i];}intmain(){floatw[20];floatcl，c2,k;intn，bestx[20];cout<〈"输入箱子数量：";cin

7、〉〉n;cout〈〈〃输入各箱子重量：〃for(inti二1;i〈二n;i++)cin〉〉w[i];Cout<<"分别输入船1,船2载重量：";cin〉>cl〉>c2;k=Maxloading(w,cl,c2,n,bestx);if(k!=-l)cout<〈〃最优装载量：〃<entsandSettingsAd>inistratorlyDocuaentsC-FreeTe>i输入集卷稽数量智轮船载重量：3100W入Sfe耀