《动态规划-背包及最优二叉树课件》由会员分享，可在线阅读，更多相关《动态规划-背包及最优二叉树课件（38页珍藏版）》请在金锄头文库上搜索。
1、0/1背包,2,0-1背包问题,所谓0/1背包问题是指在物品不能分割，只能整件装入背包或不装入的情况下，求一种最佳装载方案使得总收益最大. 给定n种物品和一背包,物品编号从1到n。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大. 0-1背包问题是一个特殊的整数规划问题。,最优子结构 0/1背包的最优解具有最优子结构特性。 设 (x1, x2, , xn)，xi0,1是0/1背包的最优解，那么，(x1 ,x2, , xn-1) 必然是0/1背包子问题的最优解：背包载重Cwnxn，共有n-1件物品，第i件物品的重量为 wi，效益Vi，w
2、i0，vi0，1in。,2 动态规划法求解,4,0-1背包问题,设所给0-1背包问题的子问题,的最优值为m(i，j)，即m(i，j)是背包容量为j，可选择物品为1，2，i时0-1背包问题的最优值。由0-1背包问题的最优子结构性质，可以建立计算m(i，j)的递归式如下。,假如有容量为9的背包，要装入4种体积为2，3，4和5的物品，价值分别为3，4，5和7。 要在不超出背包容量的前提下，用某种方法尽可能多地在背包内装入物品，使总价值最大， 首先，准备一个标号为0到4共5行和标号从0起到9共10列的空的矩形表,接着用值0初始化0列和0行的元素 按如下办法直接填行1的值：m1，j=3(第一种物品的价值
3、)，当且仅当j2(第一种物品的体积)。 第二行中的每项m2,j有两种可能性，第一种可能性是置 m2，j=m1,j这相当于把第一种物品放入背包，号物品放不下；第二种可能性是置m2,j=m1,j-3+4,它相当于加上第二种物品，使它或者仅包含第二种物品，或者同时包含第一种和第二种物品。当然，仅当j3时，才有可能加上第二种物品。继续这种方法，填入第3行和第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有两个
4、较明显的缺点： 1.算法要求所给物品的重量w是整数 2.当背包容量c很大时，算法需要的计算时间比较多。,9,算法改进,由m(i,j)的递归式容易证明，在一般情况下，对每一个确定的i(1in)，函数m(i,j)是关于变量j的阶梯状单调不减函数。跳跃点是这一类函数的描述特征。在一般情况下，函数m(i,j)由其全部跳跃点唯一确定。如图所示。,对每一个确定的i(1in)，用一个表pi存储函数m(i，j)的全部跳跃点。表pi可依计算m(i，j)的递归式递归地由表pi+1计算，初始时pn+1=(0，0)。,10,一个例子,n=3，c=6，w=4，3，2，v=5，2，1。,11,函数m(i,j)是由函数m(
5、i+1,j)与函数m(i+1,j-wi)+vi作max运算得到的。因此，函数m(i,j)的全部跳跃点包含于函数m(i+1，j)的跳跃点集pi+1与函数m(i+1，j-wi)+vi的跳跃点集qi+1的并集中。易知，(s,t)qi+1当且仅当wisc且(s-wi,t-vi)pi+1。因此，容易由pi+1确定跳跃点集qi+1如下qi+1=pi+1(wi,vi)=(j+wi,m(i,j)+vi)|(j,m(i,j)pi+1 另一方面，设(a，b)和(c，d)是pi+1qi+1中的2个跳跃点，则当ca且db时，(c，d)受控于(a，b)，从而(c，d)不是pi中的跳跃点。除受控跳跃点外，pi+1qi+1
6、中的其它跳跃点均为pi中的跳跃点。 由此可见，在递归地由表pi+1计算表pi时，可先由pi+1计算出qi+1，然后合并表pi+1和表qi+1，并清除其中的受控跳跃点得到表pi。,算法改进,12,一个例子,n=5，c=10，w=2，2，6，5，4，v=6，3，5，4，6。,初始时p6=(0,0)，(w5,v5)=(4,6)。因此，q6=p6(w5,v5)=(4,6)。 p5=(0,0),(4,6)。 q5=p5(w4,v4)=(5,4),(9,10)。从跳跃点集p5与q5的并集p5q5=(0,0),(4,6),(5,4),(9,10)中看到跳跃点(5,4)受控于跳跃点(4,6)。将受控跳跃点(5
7、,4)清除后，得到p4=(0,0),(4,6),(9,10) q4=p4(6，5)=(6，5)，(10，11) p3=(0，0)，(4，6)，(9，10)，(10，11) q3=p3(2，3)=(2，3)，(6，9) p2=(0，0)，(2，3)，(4，6)，(6，9)，(9，10)，(10，11) q2=p2(2，6)=(2，6)，(4，9)，(6，12)，(8，15) p1=(0，0)，(2，6)，(4，9)，(6，12)，(8，15) p1的最后的那个跳跃点(8,15)给出所求的最优值为m(1,c)=15。,13,上述算法的主要计算量在于计算跳跃点集pi(1in)。由于qi+1=pi+1
8、(wi，vi)，故计算qi+1需要O(|pi+1|)计算时间。合并pi+1和qi+1并清除受控跳跃点也需要O(|pi+1|)计算时间。从跳跃点集pi的定义可以看出，pi中的跳跃点相应于xi,xn的0/1赋值。因此，pi中跳跃点个数不超过2n-i+1。由此可见，算法计算跳跃点集pi所花费的计算时间为 从而，改进后算法的计算时间复杂性为O(2n)。当所给物品的重量wi(1in)是整数时，|pi|c+1，(1in)。在这种情况下，改进后算法的计算时间复杂性为O(minnc,2n)。,算法复杂度分析,最优二叉搜索树,二叉搜索树的基本操作,查找 插入 删除,设有元素集合S=x1,x2,xn，其中，x1x
9、2xn。表示有序集S的二叉搜索树利用二叉树的结点来存储有序集中的元素。 二叉搜索树的叶子结点是形如（ xi,xi+1 ）的开区间。 在表示S的二叉搜索树中搜索一个元素x，返回的结果有两种情形： （1）在二叉搜索树的内结点中找到x=xi （2）在二叉搜索树的叶子结点中确定x属于（ xi,xi+1 ）,1 问题描述,22,最优二叉搜索树,二叉搜索树,（1）若它的左子树不空，则左子树上所有 节点的值均小于它的根节点的值； （2）若它的右子树不空，则右子树上所有 节点的值均大于它的根节点的值； （3 它的左、右子树也分别为二叉排序树,在随机的情况下，二叉查找树的平均查找长度 和 是等数量级的,p(i)
10、 是在集合中成功查找xi 的概率，1i n，q(i)是待查元素x值满足 xixxi+1的概率,0i n（假定x0= , xn+1=+）。 最优二叉搜索树问题是指设法构造一棵具有最小平均搜索时间的二叉搜索树。,设 c(0,n) 是由元素值集合a1,an所构造的最优二叉搜索树的代价，则,2动态规划法求解,一般地，c(i,j) ,ij 是元素值集合ai+1,aj所构造的最优二叉搜索树的代价，设r(i,j)=k为该树的根，要求结点k满足,例 设n4且（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都已乘
11、了16。,构造最优二叉搜索树 int Find(int i,int j,int *r,float*c) float min=INFTY; int k; for (int m=i+1;m=j;m+) if (cim-1+cmj)min) min=cim-1+cmj;k=m; return k; ,最优二叉搜索树算法,void CreateOBST(float* p,float* q, float *c,int *r,float*w,int n) for (int i=0;i=n-1;i+) wii=qi;cii=0.0;rii=0; wii+1=qi+qi+1+pi+1; cii+1=qi+qi
12、+1+pi+1; rii+1=i+1; wnn=qn;cnn=0.0;rnn=0;,for (int m=2;m=n;m+) for (i=0;i=n-m;i+) int j=i+m; wij=wij-1+pj+qj; int k = Find(i,j,r,c); cij = wij + cik-1 + ckj; rij = k; ,31,搜索成功与不成功的概率 二搜索树的期望耗费 有 个节点的二叉树的个数为： 穷举搜索法的时间复杂度为指数级,二叉搜索树的期望耗费,32,二叉搜索树的期望耗费示例,33,最优二叉搜索树,最优二叉搜索树Tij的平均路长为pij，则所求的最优值为p1,n。由最优二叉
13、搜索树问题的最优子结构性质可建立计算pij的递归式如下 记wi,jpi,j为m(i,j)，则m(1,n)=w1,np1,n=p1,n为所求的最优值。计算m(i,j)的递归式为 注意到， 可以得到O(n2)的算法,计算所有Sj和S1j的步骤如下： S-1=(0,0)，函数f(-1,X)只有一个阶跃点； S1j=(X,P)|(X-wj,P-pj)Sj1，也就是说，由集合Sj-1中的每个阶跃点（X,P），得到集合S1j中的一个阶跃点（X+wj,P+pj）； Sj是合并集合Sj-1S1j，舍弃其中被支配的阶跃点和所有XM的阶跃点得到。,S1=(0,0)，S10=(2,1) S0=(0,0),(2,1)
14、，S11=(3,2),(5,3) S1=(0,0),(2,1),(3,2),(5,3)， S12=(4,4),(6,5)，(7,6),(9,7) S2=(0,0),(2,1),(3,2),(4,4),(6,5),背包算法的粗略描述 void DKP(float *p,float *w,int n, float M, float ,(X1,P1)=Sn2中最后一个阶跃点; (X2,P2)=(X+wn1,P+pn1)，其中(X,P)是Sn-1 中 使得 X+wn1M的最大的阶跃点; PmaxP1,P2; If (P2P1) xn1=1; else xn1=0; 回溯确定xn2,xn-3,x0; ,性能分析,在最坏情况下，算法的空间复杂度是O(2n)。 在最坏情况下，算法的时间复杂度是O(2n)。,
