动态规划-背包及最优二叉树

20-1背包问题所谓0/1背包问题是指在物品不能分割，只能整件装入背包或不装入的情况下，求一种最佳装载方案使得总收益最大.给定n种物品和一背包,物品编号从1到n。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大.0-1背包问题是一个特殊的整数规划问题。niiixv1maxnixCxwiniii1},1,0{1最优子结构0/1背包的最优解具有最优子结构特性。设(x1,x2,…,xn)，xi{0,1}是0/1背包的最优解，那么，(x1,x2,…,xn-1)必然是0/1背包子问题的最优解：背包载重Cwnxn，共有n-1件物品，第i件物品的重量为wi，效益Vi，wi0，vi0，1in。40-1背包问题设所给0-1背包问题的子问题nikkkxvmaxnkixjxwknikkk},1,0{的最优值为m(i，j)，即m(i，j)是背包容量为j，可选择物品为1，2，…，i时0-1背包问题的最优值。由0-1背包问题的最优子结构性质，可以建立计算m(i，j)的递归式如下。0j或00,0),1(}),1(),,1(max{),(iwjiwjjimvwjimjimjimiiii假如有容量为9的背包，要装入4种体积为2，3，4和5的物品，价值分别为3，4，5和7。要在不超出背包容量的前提下，用某种方法尽可能多地在背包内装入物品，使总价值最大，首先，准备一个标号为0到4共5行和标号从0起到9共10列的空的矩形表,接着用值0初始化0列和0行的元素按如下办法直接填行1的值：m[1，j]=3(第一种物品的价值)，当且仅当j≥2(第一种物品的体积)。第二行中的每项m[2,j]有两种可能性，第一种可能性是置m[2，j]=m[1,j]这相当于把第一种物品放入背包，２号物品放不下；第二种可能性是置m[2,j]=m[1,j-3]+4,它相当于加上第二种物品，使它或者仅包含第二种物品，或者同时包含第一种和第二种物品。当然，仅当j≥3时，才有可能加上第二种物品。继续这种方法，填入第3行和第4行，得到如图所示的表。列号行列号012345678900000000000100333333332003447777730034478991240034578101112图背包问题算法的一个例子每种物品只一件第9列的第ｉ项,也就是Ｖ[ｉ,9],包含通过用前ｉ个物品来装背包可以得到的最大价值,这样,在最后一列的最后一项找到最优解,通过装物品3和4达到。还存在着装物品1,2和3的另一个最优解，这个解对应于表中的m[3，9]，它是在考虑第4种物品前的最优解。体积为2，3，4和5的物品，价值分别为3，4，5和7。容量为9的背包作业设有0/1背包问题n=3，（w1,w2,w3）=（2,3,4），（v1,v2,v3）=（1,2,4）和C=6。Knapsack有两个较明显的缺点：1.算法要求所给物品的重量w是整数2.当背包容量c很大时，算法需要的计算时间比较多。9算法改进由m(i,j)的递归式容易证明，在一般情况下，对每一个确定的i(1≤i≤n)，函数m(i,j)是关于变量j的阶梯状单调不减函数。跳跃点是这一类函数的描述特征。在一般情况下，函数m(i,j)由其全部跳跃点唯一确定。如图所示。对每一个确定的i(1≤i≤n)，用一个表p[i]存储函数m(i，j)的全部跳跃点。表p[i]可依计算m(i，j)的递归式递归地由表p[i+1]计算，初始时p[n+1]={(0，0)}。10一个例子n=3，c=6，w={4，3，2}，v={5，2，1}。x(0,0)m(4,x)x(2,1)m(4,x-2)+1x(0,0)(2,1)m(3,x)(3,2)xm(3,x-3)+2(5,3)x(0,0)(2,1)m(2,x)(3,2)(5,3)xm(2,x-4)+5(4,5)(6,6)(7,7)(9,8)x(0,0)(2,1)m(1,x)(3,2)(5,3)(4,5)(6,6)(7,7)(9,8)x(0,0)(2,1)m(3,x)x(0,0)(2,1)m(2,x)(3,2)(5,3)11•函数m(i,j)是由函数m(i+1,j)与函数m(i+1,j-wi)+vi作max运算得到的。因此，函数m(i,j)的全部跳跃点包含于函数m(i+1，j)的跳跃点集p[i+1]与函数m(i+1，j-wi)+vi的跳跃点集q[i+1]的并集中。易知，(s,t)q[i+1]当且仅当wisc且(s-wi,t-vi)p[i+1]。因此，容易由p[i+1]确定跳跃点集q[i+1]如下q[i+1]=p[i+1](wi,vi)={(j+wi,m(i,j)+vi)|(j,m(i,j))p[i+1]}•另一方面，设(a，b)和(c，d)是p[i+1]q[i+1]中的2个跳跃点，则当ca且db时，(c，d)受控于(a，b)，从而(c，d)不是p[i]中的跳跃点。除受控跳跃点外，p[i+1]q[i+1]中的其它跳跃点均为p[i]中的跳跃点。•由此可见，在递归地由表p[i+1]计算表p[i]时，可先由p[i+1]计算出q[i+1]，然后合并表p[i+1]和表q[i+1]，并清除其中的受控跳跃点得到表p[i]。算法改进12一个例子n=5，c=10，w={2，2，6，5，4}，v={6，3，5，4，6}。初始时p[6]={(0,0)}，(w5,v5)=(4,6)。因此，q[6]=p[6](w5,v5)={(4,6)}。p[5]={(0,0),(4,6)}。q[5]=p[5](w4,v4)={(5,4),(9,10)}。从跳跃点集p[5]与q[5]的并集p[5]q[5]={(0,0),(4,6),(5,4),(9,10)}中看到跳跃点(5,4)受控于跳跃点(4,6)。将受控跳跃点(5,4)清除后，得到p[4]={(0,0),(4,6),(9,10)}q[4]=p[4](6，5)={(6，5)，(10，11)}p[3]={(0，0)，(4，6)，(9，10)，(10，11)}q[3]=p[3](2，3)={(2，3)，(6，9)}p[2]={(0，0)，(2，3)，(4，6)，(6，9)，(9，10)，(10，11)}q[2]=p[2](2，6)={(2，6)，(4，9)，(6，12)，(8，15)}p[1]={(0，0)，(2，6)，(4，9)，(6，12)，(8，15)}p[1]的最后的那个跳跃点(8,15)给出所求的最优值为m(1,c)=15。13上述算法的主要计算量在于计算跳跃点集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]中跳跃点个数不超过2n-i+1。由此可见，算法计算跳跃点集p[i]所花费的计算时间为从而，改进后算法的计算时间复杂性为O(2n)。当所给物品的重量wi(1≤i≤n)是整数时，|p[i]|≤c+1，(1≤i≤n)。在这种情况下，改进后算法的计算时间复杂性为O(min{nc,2n})。算法复杂度分析nniinniOOipO22|]1[|22查找插入删除设有元素集合S={x1,x2,…,xn}，其中，x1x2…xn。表示有序集S的二叉搜索树利用二叉树的结点来存储有序集中的元素。二叉搜索树的叶子结点是形如（xi,xi+1）的开区间。在表示S的二叉搜索树中搜索一个元素x，返回的结果有两种情形：（1）在二叉搜索树的内结点中找到x=xi（2）在二叉搜索树的叶子结点中确定x属于（xi,xi+1）22最优二叉搜索树二叉搜索树（1）若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值；（2）若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值；（3它的左、右子树也分别为二叉排序树45125333724100619078在随机的情况下，二叉查找树的平均查找长度和是等数量级的nlogp(i)是在集合中成功查找xi的概率，1in，q(i)是待查元素x值满足xixxi+1的概率,0in（假定x0=,xn+1=+）。最优二叉搜索树问题是指设法构造一棵具有最小平均搜索时间的二叉搜索树。niniiqip101)()(设c(0,n)是由元素值集合{a1,…,an}所构造的最优二叉搜索树的代价，则n)w(0,}n)c(k,1)kc(0,{min}n)c(k,1)kc(0,n)w(0,{minn)c(0,nk1nk1一般地，c(i,j),ij是元素值集合{ai+1,…,aj}所构造的最优二叉搜索树的代价，设r(i,j)=k为该树的根，要求结点k满足)jw(i,}j)c(k,1)kc(i,{min}j)c(k,1)kc(i,j){w(i,minj)c(i,jk1ijk1i例设n＝4且（a1,a2,a3,a4）=(Mon,Thu,Tue,Wed)。又设p(1:4)=(3,3,1,1)和q(0:4)＝(2,3,1,1,1)。这里p和q都已乘了16。构造最优二叉搜索树intFind(inti,intj,int**r,float**c){floatmin=INFTY;intk;for(intm=i+1;m=j;m++)if((c[i][m-1]+c[m][j])min){min=c[i][m-1]+c[m][j];k=m;}returnk;}voidCreateOBST(float*p,float*q,float**c,int**r,float**w,intn){for(inti=0;i=n-1;i++){w[i][i]=q[i];c[i][i]=0.0;r[i][i]=0;w[i][i+1]=q[i]+q[i+1]+p[i+1];c[i][i+1]=q[i]+q[i+1]+p[i+1];r[i][i+1]=i+1;}w[n][n]=q[n];c[n][n]=0.0;r[n][n]=0;for(intm=2;m=n;m++)for(i=0;i=n-m;i++){intj=i+m;w[i][j]=w[i][j-1]+p[j]+q[j];intk=Find(i,j,r,c);c[i][j]=w[i][j]+c[i][k-1]+c[k][j];r[i][j]=k;}})n(O)n(O)1mn(m)n(Om3n2mn2mmn0i31搜索成功与不成功的概率二搜索树的期望耗费有个节点的二叉树的个数为：穷举搜索法的时间复杂度为指数级110niniiiqpniiiTniiiTniiiTniiiTqdpkqdpkTE0101)(depth)(depth1)1)(depth()1)(depth()incostsearch(n)/4(2/3nn二叉搜索树的期望耗费0d1d2d3d4d5d1k2k3k4k5k322.80Total0.400.1030.200.0530.200.0530.200.0530.300.1020.150.0520.600.2020.200.1010.150.0520.100.1000.300.151oncontributiyprobabilitdepthnode54321054321ddddddkkkkk0d1d2d3d4d5d1k2k3k4k5k二叉搜索树的期望耗费示例33最优二叉搜索树最优二叉搜索树Tij的平均路长为pij，则所求的最优值为p1,n。由最优二叉搜索树问题的最优子结构性质可建立计算pij的递归式如下记wi,jpi,j为m(i,j)，则m(1,n)=w1,np1,n=