動態(tài)規(guī)劃0-1背包的改進(jìn)算法java代碼.doc

《動態(tài)規(guī)劃0-1背包的改進(jìn)算法java代碼.doc》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、importjava.lang.*;importjava.io.*;publicclassSiyu{publicstaticvoidTraceback(intn,intw[],intv[],intp[][],int[]head,intx[]){intj=p[head[0]-1][0],m=p[head[0]-1][1];for(inti=1;i<=n;i++){x[i]=0;for(intk=head[i+1];k<=head[i]-1;k++){if(p[k][0]+w[i]==j&&p[k][1]+v[i]==m){x[i]=1;j=p[k][0];m=p[k][1];break

2、;}}}}publicstaticintknapsack(intn,intc,intv[],intw[],intp[][],intx[])//p[i][0]表示跳躍點(diǎn)的j值，p[i][1]表示跳躍點(diǎn)的m(i,j)值{int[]head=newint[n+2];//head[i]表示p[i]中點(diǎn)在數(shù)組p中的起始位置，head[0]沒用head[n+1]=0;p[0][0]=0;p[0][1]=0;intleft=0,right=0,next=1;//（left..right）表示p[i+1]中點(diǎn)在數(shù)組p中的上下界，next表示p[i]中的點(diǎn)在數(shù)組p中的插入位置head[n]=1;for

3、(inti=n;i>=1;i--){//形成p[i]中的點(diǎn)intk=left;//p[k]表示p[i+1]中點(diǎn)，p[next]表示p[i]中點(diǎn)for(intj=left;j<=right;j++){//形成q[i+1]中的點(diǎn)if(p[j][0]+w[i]>c)break;inty=p[j][0]+w[i],m=p[j][1]+v[i];//處理q[i+1]中點(diǎn)(y,m)while(k<=right&&p[k][0]

4、&&p[k][0]==y){//處理p[i+1]中與y相同的已有點(diǎn)，需比較價值的大小if(mp[next-1][1])//插入(y,m)到p[i]中{p[next][0]=y;p[next++][1]=m;}while(k<=right&&p[k][1]<=p[next-1][1])k++;//消除多個受控點(diǎn)}//endforjwhile(k<=right){//插入所有(y,m)后，原p[i+1]中比y大的點(diǎn)插入到p[i]中p[next][0]=p[k][0];p[next++][1]=p[k++][1];}left=rig

5、ht+1;right=next-1;head[i-1]=next;}System.out.print("跳躍點(diǎn)為：");for(inti=0;i

6、p[][]=newint[21][21];intx[]=newint[6];intmaxV=knapsack(n,c,v,w,p,x);System.out.println("最大值是:"+maxV);System.out.print("最優(yōu)解是:");for(inti=0;i<=n;i++)System.out.print(""+x[i]);}}