回溯法装载问题

class Loading {

friend int MaxLoading(int [] ,int ,int ,int []);

private:

//int Bound(int i); void Backtrack(int t); int n;//¼¯×°ÏäÊý int *x;//µ±Ç°½â

int *bestx;//µ±Ç°×îÓŽâ int *w;//¼¯×°ÏäÖØÁ¿Êý×é int c;//µÚÒ»ËÒÂÖ´¬µÄÔØÖØÁ¿ int cw;//µ±Ç°ÖØÁ¿

int bestw;//µ±Ç°×îÓÅÔØÖØÁ¿ int r;//Ê£Ó༯װÏäÖØÁ¿ };

void Loading::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]; }

int MaxLoading(int w[],int c,int n,int bestx[]){ Loading X;

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; }

void main(){

int *w;

int *bestx; int n; int c;

cout<<\"ÇëÊäÈ뼯װÏäÊý:\"; cin>>n;

cout<<\"ÇëÊäÈëµÚÒ»ËÒÂÖ´¬ÔØÖØÁ¿:\"; cin>>c;

w=new int[n+1]; w[0]=0;

cout<<\"ÇëÊäÈëÖØÁ¿:\"<>w[i];

bestx=new int[n+1]; for(i=1;i<=n;i++) bestx[i]=0;

int m=MaxLoading(w,c,n,bestx); cout<<\"×î´ó×°ÔØÊýÁ¿:\"<