装载问题装载问题

1、算法设计：
回溯法，用子集树表示其解空间；

template class Loading { public: void Backtrack(int i); int n, *x, *bestx; Type *w, c, cw, bestw, r; }; template voidLoading ::Backtrack (int i); template Type MaxLoading(Type w[], Type c, int n, int bestx[]);

【装载问题】2、上界函数：

template voidLoading ::Backtrack (int i) { if (i > n) { if (cw>bestw) { for(int j=1; j<=n; j++) { bestx[j]=x[j]; bestw=cw; } } return; }r-=w[i]; if (cw + w[i] <= c) { x[i] = 1; cw += w[i]; Backtrack(i+1); cw-=w[i]; }if (cw + r > bestw) { x[i] = 0; Backtrack(i + 1); } r+=w[i]; }template Type MaxLoading(Type w[], Type c, int n, int bestx[]) { LoadingX; X.x=new int[n+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+=w[i]; } X.Backtrack(1); delete []X.x; return X.bestw; }