回溯法装载问题.doc

《回溯法装载问题.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、#includeusingnamespacestd;classLoading{friendintMaxLoading(int[],int,int,int[]);private://intBound(inti);voidBacktrack(intt);intn;//¼¯×°ÏäÊýint*x;//µ±Ç°½âint*bestx;//µ±Ç°×îÓŽâint*w;//¼¯×°ÏäÖØÁ¿Êý×éintc;//µÚÒ»ËÒÂÖ´¬µÄÔØÖØÁ¿intcw;//µ±Ç°ÖØÁ¿intbestw;//µ±Ç°×îÓÅÔØÖØÁ¿intr;//Ê£Ó༯×

2、°ÏäÖØÁ¿};voidLoading::Backtrack(inti){if(i>n){if(cw>bestw){for(intj=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];}intMaxLoading(intw[],intc,intn,intbestx[]){LoadingX;X.x=newint[n+1

3、];X.w=w;X.c=c;X.n=n;X.bestx=bestx;X.bestw=0;X.cw=0;X.r=0;for(inti=1;i<=n;i++)X.r+=w[i];X.Backtrack(1);delete[]X.x;returnX.bestw;}voidmain(){int*w;int*bestx;intn;intc;cout<<"ÇëÊäÈ뼯װÏäÊý:";cin>>n;cout<<"ÇëÊäÈëµÚÒ»ËÒÂÖ´¬ÔØÖØÁ¿:";cin>>c;w=newint[n+1];w[0]=0;cout<<"ÇëÊäÈëÖØÁ¿:"<

4、nti=1;i<=n;i++)cin>>w[i];bestx=newint[n+1];for(i=1;i<=n;i++)bestx[i]=0;intm=MaxLoading(w,c,n,bestx);cout<<"×î´ó×°ÔØÊýÁ¿:"<