实验八回溯算法.doc

实验八 回溯算法（4学时）一、实验目的与要求1、掌握装载问题的回溯算法；2、初步掌握回溯算法；二、实验题有一批共n个集装箱要装上2艘载重量分别为c1和c2的轮船，其中集装箱i的重量为wi，且 装载问题要求确定是否有一个合理的装载方案可将这个集装箱装上这2艘轮船。如果有，找出一种装载方案。三、实验提示装载问题 问题描述有一批共n个集装箱要装上2艘载重量分别为c1和c2的轮船，其中集装箱i的重量为wi ，且 ，要求确定是否有一个合理的装载方案可将这n个集装箱装上这2艘轮船。如果有，请给出该方案。 编程任务 利用回溯法试设计一个算法求出该装载问题的解。 数据输入由文件input.txt提供输入数据。文件的第1行中有2个正整数n及c，表示有n个集装箱，第一艘船的载重量为c。接下来的一行为每个集装箱的重量。 结果输出 程序运行结束时，将计算出的最优解输出到文件output.txt中，如果某集装箱被装入船上，则对应的解为1，如果不能装入则为0。输入文件示例输出文件示例input.txtoutput.txt3 3016 15 150 1 1代码：#include#include#includeint result;int nn,cc;int *ww,*superbestx,*superbestw;templateclass Loadingfriend Type Maxloading(Type,Type,int,int);public: void Backtrack(int i); int n,/集装箱数 *x,/当前解 *bestx;/当前最优解 Type* w,/集装箱重量数组 c,/第一艘轮船的载重量 cw,/当前载重量 bestw,/当前最优载重量 r;/剩余集装箱重量;templatevoid Loading:Backtrack(int i)/搜索第i层结点if(in)/到达叶结点 if(cwbestw) for(int j=1;j=n;j+) bestxj=xj; bestw =cw; return;/搜索子树r-=wi;if(cw + wi) bestw)/ xi=0; Backtrack(i+1);r+=wi;templateType Maxloading(Type w,Type c, int n,int bestx)/返回最优载重量Loading X;/X.x = new intn+1;X.w = w;X.c = c;X.n = n;X.bestx = bestx;X.bestw = 0;X.cw = 0;/X.r = 0;for(int i=1;i=n;i+) X.r+=wi;/初始时r为全体物品的重量和/计算最优载重量X.Backtrack(1);delete X.x;for(int k=0;kn;k+) superbestxk = X.bestxk;result=X.bestw;/ delete X.x;return result;int main(int argc,int *argv)/ Loading X;ifstream in(input.txt);/打开输入文件 ofstream out(output.txt);/打开输出文件innn;/集装箱数incc;/第一艘轮船的载重量ww = (int *)malloc(sizeof(int)*nn);superbestx = (int *)malloc(sizeof(int)*nn);/ superbestw = (int *)malloc(sizeof(int)*nn);for(int i=0;iwwi;/集装箱重量数组 superbestxi=0;/初始当前化最优解Maxloading(ww,cc,nn, superbestx);for(int kk=0;kknn;kk+) outsuperbestxkkt;/将最优解写入输出文件outendl;sys