0019算法笔记――0-1背包问题动态规划求解(三)

return p[next-1][1];

}

//x[]数组存储对应物品0-1向量,0不装入背包，1表示装入背包

template

void Traceback(int n,Type w[],Type v[],Type **p,int *head,int x[])

{

//初始化j,m为最后一个跳跃点对应的第0列及第1列

//如上例求出的 最后一个跳跃点为（8 15）j=8,m=15

Type 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）

{

//判断物品i是否装入，如上例与跳跃点(6 9)相加等于（8 15）所以1装入

if(p[k][0]+w[i]==j && p[k][1]+v[i]==m)

{

x[i]=1;//物品i被装入，则x[i]置1

j=p[k][0];// j和m值置为满足if条件的跳跃点对应的值

m=p[k][1];// 如上例j=6,m=9

break;//再接着判断下一个物品

}

}

}

}

上述算法的主要计算量在于计算跳跃点集p[i](1≤i≤n)。由于q[i+1]=p[i+1] (wi，vi)，故计算q[i+1]需要O(|p[i+1]|)计算时间。合并p[i+1]和q[i+1]并清除受控跳跃点也需要O(|p[i+1]|)计算时间。从跳跃点集p[i]的定义可以看出，p[i]中的跳跃点相应于xi,…,xn的0/1赋值。因此，p[i]中跳跃点个数不超过2^(n-i+1)。由此可见，算法计算跳跃点集p[i]所花费的计算时间为从而，改进后算法的计算时间复杂性为O(2^n)。当所给物品的重量wi(1≤i≤n)是整数时，|p[i]|≤c+1，(1≤i≤n)。在这种情况下，改进后算法的计算时间复杂性为O(min{nc,2^n})。

运行结果如图：