动态规划0-1背包的改进算法java代码.doc

《动态规划0-1背包的改进算法java代码.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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]表示跳跃点的j值，p[i][1]表示跳跃点的m(i,j)值{int[]head=newint[n+2];//head[i]表示p[i]中点在数组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]中点在数组p中的上下界，next表示p[i]中的点在数组p中的插入位置head[n]=1;for

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

4、&&p[k][0]==y){//处理p[i+1]中与y相同的已有点，需比较价值的大小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++;//消除多个受控点}//endforjwhile(k<=right){//插入所有(y,m)后，原p[i+1]中比y大的点插入到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("跳跃点为：");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("最优解是:");for(inti=0;i<=n;i++)System.out.print(""+x[i]);}}