1、 1 2(3.4.1) max 1niiixvnixCxwtsiniii1,1 , 0 .1 給定n種物品和一背包。物品i的重量是wi，其價(jià)值為vi，背包的容量為C。問(wèn):應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價(jià)值最大?0-1背包問(wèn)題描述:給定c 0, wi 0, vi 0 , 1in.要求找一n元向量(x1,x2,xn,), xi0,1, wi xic,且 vi xi達(dá)最大.即一個(gè)特殊的整數(shù)規(guī)劃問(wèn)題。 3 最優(yōu)性原理最優(yōu)性原理:設(shè)(y1,y2,yn)是 (3.4.1)的一個(gè)最優(yōu)解.則(y2,yn)是下面相應(yīng)子問(wèn)題的一個(gè)最優(yōu)解: niiixv2maxnixywCxwiniii2 ,1

2、, 0s.t 112 證明證明:使用反證法. 若不然,設(shè)(z2,z3,zn)是上述子問(wèn)題的一個(gè)最優(yōu)解,而(y2,y3,yn)不是它的最優(yōu)解.顯然有 vizi viyi (i=2,n)且 w1y1+ wizi c因此 v1y1+ vizi (i=2,n) viyi, (i=1,n) 說(shuō)明(y1,z2, z3,zn)是(3-4-1)0-1背包問(wèn)題的一個(gè)更優(yōu)解,導(dǎo)出(y1,y2,yn)不是背包問(wèn)題的最優(yōu)解,矛盾. 4 設(shè)所給0-1背包問(wèn)題的子問(wèn)題(3.4.2) nikkkxvmax nkixjxwtsknikkk,.10 的最優(yōu)值為m(i，j)，即m(i，j)是背包容量為j，可選擇物品為i，i+1，

3、n時(shí)0-1背包問(wèn)題的最優(yōu)值。由0-1背包問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)，可以建立計(jì)算m(i，j)的遞歸式:).(),(),(),(max),(343 0111iiiiwjwjjimvwjimjimjim (3.4.4) 00nnnwjwjvjnm ),( 5注注:(3-4-3)式此時(shí)背包容量為j，可選擇物品為i。此時(shí)在對(duì)xi作出決策之后,問(wèn)題處于兩種狀態(tài)之一:u背包剩余容量是j,沒(méi)產(chǎn)生任何效益;u剩余容量j-wi,效益值增長(zhǎng)了vi .從n推至i+1,i算出最優(yōu)值m(i,j) （ i=n,1） 。 m(1,c)為最優(yōu)值。然后用回溯法Traceback找出最優(yōu)解xi 其中i，c為整值。)3 . 4 . 3(

4、 (2) 0(1) ), 1(), 1(), 1(max),(iiiiwjwjjimvwjimjimjim(3.4.4) (2) 0(1) 0),(nnnwjwjvjnm3.3.算法復(fù)雜度分析：算法復(fù)雜度分析：從m(i，j)的遞歸式容易看出，算法Knapsack需要O(nc)計(jì)算時(shí)間; Traceback需O（n）計(jì)算時(shí)間 ；算法總體需要O(nc)計(jì)算時(shí)間。當(dāng)背包容量c很大時(shí)，算法需要的計(jì)算時(shí)間較多。例如，當(dāng)c2n時(shí)，算法需要(n2n)計(jì)算時(shí)間。 6templatevoid Knapsack( Type v, int w, int c, int n, Type *m) int jMax = m

5、in(wn1, c) /背包剩余容量背包剩余容量/ for(int j = 0; j=jMax; j+) /背包不同剩余容量背包不同剩余容量j jMaxc/ mnj=0; for(int j=wn; jc/ mnj=vn; for(int i=n-1; i1; i-) jMax=min(wi-1, c); for(int j=0; j=jMax; j+) /背包不同剩余容量背包不同剩余容量j jMaxc/ mij=mi+1j; /沒(méi)產(chǎn)生任何效益沒(méi)產(chǎn)生任何效益/ for(int j=wi; jc/ mij=max(mi+1j, mi+1j-wi+vi); /效益值增長(zhǎng)效益值增長(zhǎng)vi / 背包問(wèn)題

6、的動(dòng)態(tài)規(guī)劃背包問(wèn)題的動(dòng)態(tài)規(guī)劃算法算法Knapsack如下：如下： 7 m1c=m2c; if(c=w1) m1c=max(m1c, m2c-w1+v1);Template /求最優(yōu)解求最優(yōu)解xi /void Traceback(Type *m, int w, int c, int n, int x) for(int i=1; in; i+) if(mic=mi+1c) xi=0; else xi=1; c= c- wi; xn=(mnc)?1:0;說(shuō)明說(shuō)明:當(dāng)wi為正整數(shù)時(shí)，用二維數(shù)組m來(lái)存儲(chǔ)m(i,j)相應(yīng)的最優(yōu)值。Knapsack算法的另一算法的另一缺點(diǎn)是要求所給物品缺點(diǎn)是要求所給物品的重

7、量的重量w wi（1 i n）是整數(shù)是整數(shù) 8 為克服以上缺點(diǎn)，引入階梯函數(shù)。利用序偶概念，改進(jìn)算法的計(jì)算時(shí)間復(fù)雜性為O（2n ）。而當(dāng)所給物品的重量wi是整數(shù)時(shí)，其計(jì)算時(shí)間復(fù)雜性為 （略） 。 動(dòng)態(tài)規(guī)劃的其他應(yīng)用實(shí)例（略）旅行商問(wèn)題矩陣連乘問(wèn)題系統(tǒng)可靠性設(shè)計(jì)流水線調(diào)度問(wèn)題設(shè)備更新問(wèn)題最優(yōu)二叉搜索樹(shù)圖像壓縮(min,2 )nOnc 9 動(dòng)態(tài)規(guī)劃缺陷動(dòng)態(tài)規(guī)劃缺陷：（1）無(wú)一統(tǒng)一標(biāo)準(zhǔn)模型可供應(yīng)用。利用“最優(yōu)性原理”得出遞歸關(guān)系式后，必須結(jié)合問(wèn)題的特點(diǎn)，結(jié)合其他數(shù)學(xué)技巧求解，且無(wú)統(tǒng)一處理方法。（2）數(shù)值求解中，當(dāng)問(wèn)題中的狀態(tài)變量個(gè)數(shù)太多（如有向圖中的邊數(shù)），由于計(jì)算機(jī)存儲(chǔ)量及計(jì)算速度限制而無(wú)法對(duì)付“

8、維數(shù)障礙”。 由前述可知，任一多階段決策過(guò)程中的最優(yōu)化問(wèn)題，都可以用非線性規(guī)劃方法（Nonlinear programming Methods，特殊：linear programming）模型來(lái)描述。 動(dòng)態(tài)規(guī)劃的優(yōu)越之處動(dòng)態(tài)規(guī)劃的優(yōu)越之處:（1）易于確定全局解。動(dòng)態(tài)規(guī)劃方法是一種逐步改善的方法，它把原問(wèn)題化成一系列結(jié)構(gòu)相似的最優(yōu)化子問(wèn)題，而每個(gè)子問(wèn)題的變量個(gè)數(shù)比原問(wèn)題少的多，約束集合也簡(jiǎn)單得多，故較易于確定全局最優(yōu)。特別當(dāng)處理離散類型問(wèn)題時(shí)，動(dòng)態(tài)規(guī)劃是求出全局最優(yōu)化解的唯一方法。（2）能得一族解，有利分析結(jié)果是否有用或進(jìn)行選擇（決策），且大大節(jié)省工作量。（3）能利用經(jīng)驗(yàn)，提高求解效率。動(dòng)態(tài)規(guī)劃

9、方法反映過(guò)程逐段演變的前后聯(lián)系，與實(shí)際進(jìn)程更緊密，因而在計(jì)算中能（4）有廣泛應(yīng)用背景（略） 10由m(i,j)的遞歸式容易證明，在一般情況下，對(duì)每一個(gè)確定的i(1in)，函數(shù)m(i,j)是關(guān)于變量j的階梯狀單調(diào)不減函數(shù)。跳躍點(diǎn)是這一類函數(shù)的描述特征。在一般情況下，函數(shù)m(i,j)由其全部跳躍點(diǎn)惟一確定。如圖所示。對(duì)每一個(gè)確定的i(1in)，用一個(gè)表pi存儲(chǔ)函數(shù)m(i，j)的全部跳躍點(diǎn)。表pi可依計(jì)算m(i，j)的遞歸式遞歸地由表pi+1計(jì)算，初始時(shí)pn+1=(0，0)。 11n=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

10、,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) 12函數(shù)m(i,j)是由函數(shù)m(i+1,j)與函數(shù)m(i+1,j-wi)+vi作max運(yùn)算得到的。因此，函數(shù)m(i,j)的全部跳躍點(diǎn)包含于函數(shù)m(i+1，j)的跳躍點(diǎn)集pi+1與函數(shù)m(i+1，j-wi)+vi的跳躍點(diǎn)集qi+1的并集中

11、。易知，(s,t)qi+1當(dāng)且僅當(dāng)wisc且(s-wi,t-vi)pi+1。因此，容易由pi+1確定跳躍點(diǎn)集qi+1如下qi+1=pi+1(wi,vi)=(j+wi,m(i,j)+vi)|(j,m(i,j)pi+1 另一方面，設(shè)(a，b)和(c，d)是pi+1qi+1中的2個(gè)跳躍點(diǎn)，則當(dāng)ca且db時(shí)，(c，d)受控于(a，b)，從而(c，d)不是pi中的跳躍點(diǎn)。除受控跳躍點(diǎn)外，pi+1qi+1中的其他跳躍點(diǎn)均為pi中的跳躍點(diǎn)。由此可見(jiàn)，在遞歸地由表pi+1計(jì)算表pi時(shí)，可先由pi+1計(jì)算出qi+1，然后合并表pi+1和表qi+1，并清除其中的受控跳躍點(diǎn)得到表pi。 13n=5，c=10，w=2

12、，2，6，5，4，v=6，3，5，4，6。初始時(shí)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)。從跳躍點(diǎn)集p5與q5的并集p5q5=(0,0),(4,6),(5,4),(9,10)中看到跳躍點(diǎn)(5,4)受控于跳躍點(diǎn)(4,6)。將受控跳躍點(diǎn)(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的最后的那個(gè)跳躍點(diǎn)(8,15)給出所求的最優(yōu)值為m(1,c)=15。 14上述算法的主要計(jì)算量在于計(jì)算跳躍點(diǎn)集pi(1in)。由于qi+1=pi+1(wi，vi)，故計(jì)算qi+1需要O(|pi+1|)計(jì)算時(shí)間。合并pi+1和qi+1并清除受控跳躍點(diǎn)也需要O(|pi+