P[6]={(0 0)} P[5]={(0 0),(4 ,6)} P[4]={(0 0),(4 ,6),(9,10)} P[3]={(0 0),(4 ,6),(10,11)} P[2]={(0 0),(2,3),(4 ,6),(6,9),(9,10),(10,11)} P[1]={(0 0),(2,6),(4 ,9),(6,12),(8,15) } (2 6) 0-1 背包问题程序详解 #include void traceback(int n,float w[],float v[],float p[][2],int *head,int x[]) { 初始化 j,m 为最后一个跳跃点对应的第 0 列及第 1 列 如上例求出的 最后一个跳跃点为（8 15）j=8,m=15 float j=p[head[0]-1][0], m=p[head[0]-1][1]; for(int i=1;i<=n;i++) { x[i]=0; 初始化数组； for(int k=head[i+1];k<=head[i]-1;k++) 初始 k 指向 p[2]的第一个跳跃点（0 0） if(p[k][0]+w[i]==j && p[k][1]+v[i]==m) { { w[1]=2,v[1]=6 所以 1 装入 x[i]=1; j=p[k][0]; m=p[k][1]; break; } } } } 判断物品 i 是否装入，如上例 与跳跃点(6 9)相加等于（8 15） 物品 i 被装入，则 x[i]置 1 j 和 m 值置为满足 if 条件的跳跃 点对应的值 如上例 j=6,m=9 再接着判断下一个物品 判断物品 i 是否装入,若装入对应 x[i]置 1 否则置 0； int Knapsack(int n,float c,float v[],float w[],float p[][2],int x[]) { int *head=new int[n+2]; 

head[n+1]=0; p[0][0]=0; p[0][1]=0; head[n]=1; int left=0,right=0,next=1; 最后一个 for(int i=n;i>=1;i--) 指向（9,10） { int k=left; 受控点 物品 n 的跳跃点（0,0） left 指向 p[i+1]的第一个跳跃点，right 指向 若计算 p[3]=0;则 left 指向 p[4]的第一跳跃点（0 0）right 即下一个跳跃点要存放的位置 k 指向 p[ ]中跳跃点,移动 k 来判断 p[]与 p[]+（w v）中的 for(int j=left;j<=right;j++) { if(p[j][0]+w[i]>c) break; float y=p[j][0]+w[i], m=p[j][1]+v[i]; while(k<=right && p[k][0]=y 且 m> =p[k][1] 判断是不是当前 i 的最后一个跳跃点的受控点 若不是则为 i 的跳跃点存储 } while(k<=right && p[k][1]<=p[next-1][1]) k++; 若是，则对下一个元素进行判断。 { if(mp[next-1][1]) { p[next][0]=y; p[next++][1]=m; } while(k<=right) { p[next][0]=p[k][0]; p[next++][1]=p[k++][1]; 将i+1 剩下的跳跃点作为做为i 的跳跃点存储 left=right+1; right=next-1; head[i-1]=next; 第 i-1 个物品第一个跳跃点的位置 head[0]指第 0 个 

物品第一个跳跃点的位置 } cout<<"跳跃点为："<>c>>n; cout<<"输入每种物品的重量和价值："<>w[i]>>v[i]; maxV=Knapsack(n,c,v,w,p,x); cout<<"最大价值是 : "<