動態(tài)規(guī)劃-背包及最優(yōu)二叉樹

1、2所謂0/1背包問題是指在物品不能分割，只能整件裝入背包或不裝入的情況下，求一種最佳裝載方案使得總收益最大.給定n種物品和一背包,物品編號從1到n。物品i的重量是wi，其價值為vi，背包的容量為C。問應如何選擇裝入背包的物品，使得裝入背包中物品的總價值最大.0-1背包問題是一個特殊的整數(shù)規(guī)劃問題。niiixv1maxnixCxwiniii1,1 , 01最優(yōu)子結構0/1背包的最優(yōu)解具有最優(yōu)子結構特性。設 (x1, x2, , xn)，xi0,1是0/1背包的最優(yōu)解，那么，(x1 ,x2, , xn-1) 必然是0/1背包子問題的最優(yōu)解：背包載重Cwnxn，共有n-1件物品，第i件物品的重量為

2、wi，效益Vi，wi0，vi0，1in。4設所給0-1背包問題的子問題nikkkxvmaxnkixjxwknikkk,1 , 0的最優(yōu)值為m(i，j)，即m(i，j)是背包容量為j，可選擇物品為1，2，i時0-1背包問題的最優(yōu)值。由0-1背包問題的最優(yōu)子結構性質，可以建立計算m(i，j)的遞歸式如下。0j或00,0),1(),1(),1(max),(iwjiwjjimvwjimjimjimiiii 假如有容量為假如有容量為9 9的背包，要裝入的背包，要裝入4 4種體積為種體積為2 2，3 3，4 4和和5 5的物品，的物品，價值分別為價值分別為3 3，4 4，5 5和和7 7。 要在不超出背包

3、容量的前提下，用某種方法盡可能多地在背包內要在不超出背包容量的前提下，用某種方法盡可能多地在背包內裝入物品，使總價值最大，裝入物品，使總價值最大， 首先，準備一個標號為首先，準備一個標號為0 0到到4 4共共5 5行行和標號從和標號從0 0起到起到9 9共共1010列列的空的的空的矩形表矩形表, ,接著接著用值用值0 0初始化初始化0 0列和列和0 0行行的元素的元素 按如下辦法直接填行按如下辦法直接填行1 1的值：的值：m m11，j j=3(=3(第一種物品的價值第一種物品的價值) )，當，當且僅當且僅當j2(j2(第一種物品的體積第一種物品的體積) )。 第二行中的每項第二行中的每項m2

4、,jm2,j有兩種可能性，有兩種可能性，第一種可能性第一種可能性是置是置m m22，j=j=m m1,j1,j這相當于把第一種物品放入背包，號物品放不下；這相當于把第一種物品放入背包，號物品放不下；第第二種可能性二種可能性是置是置m2,j=m2,j=m m1,j-3+4,1,j-3+4,它相當于加上第二種物品，使它它相當于加上第二種物品，使它或者僅包含第二種物品，或者同時包含第一種和第二種物品。當然，或者僅包含第二種物品，或者同時包含第一種和第二種物品。當然，僅當僅當j3j3時，才有可能加上第二種物品。繼續(xù)這種方法，填入第時，才有可能加上第二種物品。繼續(xù)這種方法，填入第3 3行行和第和第4 4

5、行，得到如圖所示的表。行，得到如圖所示的表。 列號列號體積為體積為2 2，3 3，4 4和和5 5的物品，價值分別為的物品，價值分別為3 3，4 4，5 5和和7 7。容量為容量為9 9的背包的背包設有0/1背包問題n=3，（w1,w2,w3）=（2,3,4），（v1,v2,v3）=（1,2,4）和C=6。Knapsack有兩個較明顯的缺點：1.算法要求所給物品的重量w是整數(shù)2.當背包容量c很大時，算法需要的計算時間比較多。9由m(i,j)的遞歸式容易證明，在一般情況下，對每一個確定的i(1in)，函數(shù)m(i,j)是關于變量j的階梯狀單調不減函數(shù)。跳躍點是這一類函數(shù)的描述特征。在一般情況下，函

6、數(shù)m(i,j)由其全部跳躍點唯一確定。如圖所示。對每一個確定的i(1in)，用一個表pi存儲函數(shù)m(i，j)的全部跳躍點。表pi可依計算m(i，j)的遞歸式遞歸地由表pi+1計算，初始時pn+1=(0，0)。 10n=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)(

7、9,8)x(0,0)(2,1)m(3,x)x(0,0)(2,1)m(2,x)(3,2)(5,3)11函數(shù)m(i,j)是由函數(shù)m(i+1,j)與函數(shù)m(i+1,j-wi)+vi作max運算得到的。因此，函數(shù)m(i,j)的全部跳躍點包含于函數(shù)m(i+1，j)的跳躍點集pi+1與函數(shù)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

8、中的2個跳躍點，則當ca且db時，(c，d)受控于(a，b)，從而(c，d)不是pi中的跳躍點。除受控跳躍點外，pi+1qi+1中的其它跳躍點均為pi中的跳躍點。由此可見，在遞歸地由表pi+1計算表pi時，可先由pi+1計算出qi+1，然后合并表pi+1和表qi+1，并清除其中的受控跳躍點得到表pi。12n=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),(

9、4,6),(5,4),(9,10)中看到跳躍點(5,4)受控于跳躍點(4,6)。將受控跳躍點(5,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)給出所求的最優(yōu)值為m(1,c)=15。

10、13上述算法的主要計算量在于計算跳躍點集pi(1in)。由于qi+1=pi+1(wi，vi)，故計算qi+1需要O(|pi+1|)計算時間。合并pi+1和qi+1并清除受控跳躍點也需要O(|pi+1|)計算時間。從跳躍點集pi的定義可以看出，pi中的跳躍點相應于xi,xn的0/1賦值。因此，pi中跳躍點個數(shù)不超過2n-i+1。由此可見，算法計算跳躍點集pi所花費的計算時間為從而，改進后算法的計算時間復雜性為O(2n)。當所給物品的重量wi(1in)是整數(shù)時，|pi|c+1，(1in)。在這種情況下，改進后算法的計算時間復雜性為O(minnc,2n)。 nniinniOOipO22| 1|22查

11、找插入刪除設 有 元 素 集 合 S = x1, x2, , xn ， 其 中 ，x1x2xn。表示有序集S的二叉搜索樹利用二叉樹的結點來存儲有序集中的元素。二叉搜索樹的葉子結點是形如（ xi,xi+1 ）的開區(qū)間。在表示S的二叉搜索樹中搜索一個元素x，返回的結果有兩種情形：（1）在二叉搜索樹的內結點中找到x=xi （2）在二叉搜索樹的葉子結點中確定x屬于（ xi,xi+1 ）22n二叉搜索樹（1）若它的左子樹不空，則左子樹上所有節(jié)點的值均小于它的根節(jié)點的值；（2）若它的右子樹不空，則右子樹上所有節(jié)點的值均大于它的根節(jié)點的值；（3 它的左、右子樹也分別為二叉排序樹451253337241006

12、19078在隨機的情況下，二叉查找樹的平均查找長度和 是等數(shù)量級的nlogp(i) 是在集合中成功查找xi 的概率，1i n，q(i)是待查元素x值滿足 xixxi+1的概率,0i n（假定x0= , xn+1=+）。最優(yōu)二叉搜索樹問題是指設法構造一棵具有最小平均搜索時間的二叉搜索樹。niniiqip101)()(設 c(0,n) 是由元素值集合a1,an所構造的最優(yōu)二叉搜索樹的代價，則 n)w(0, n)c(k,1)kc(0, min n)c(k,1)kc(0,n) w(0, min n)c(0,nk1nk1一般地，c(i,j) ,ij 是元素值集合ai+1,aj所構造的最優(yōu)二叉搜索樹的代價

13、，設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設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都已乘了16。構造最優(yōu)二叉搜索樹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;

14、 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+1+pi+1; rii+1=i+1; wnn=qn;cnn=0.0;rnn=0; for (int m=2;m=n;m+) for (i=0;iM的階躍點得到。 S1=(0,0)，S10=(2,1) S0=(0,0),(2,1)，S11=(3,2),(5,3)S1=(0,0),(2,1),(3,2),(5,3)，S12=(4,4),(6,5)，(7