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

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

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

4、 (2) 0(1) ), 1(), 1(), 1(max),(iiiiwjwjjimvwjimjimjim(3.4.4) (2) 0(1) 0),(nnnwjwjvjnm3.3.算法復雜度分析：算法復雜度分析：從m(i，j)的遞歸式容易看出，算法Knapsack需要O(nc)計算時間; Traceback需O（n）計算時間 ；算法總體需要O(nc)計算時間。當背包容量c很大時，算法需要的計算時間較多。例如，當c2n時，算法需要(n2n)計算時間。 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; /沒產生任何效益沒產生任何效益/ for(int j=wi; jc/ mij=max(mi+1j, mi+1j-wi+vi); /效益值增長效益值增長vi / 背包問題

6、的動態規劃背包問題的動態規劃算法算法Knapsack如下：如下： 7 m1c=m2c; if(c=w1) m1c=max(m1c, m2c-w1+v1);Template /求最優解求最優解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;說明說明:當wi為正整數時，用二維數組m來存儲m(i,j)相應的最優值。Knapsack算法的另一算法的另一缺點是要求所給物品缺點是要求所給物品的重

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

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

9、方法反映過程逐段演變的前后聯系，與實際進程更緊密，因而在計算中能（4）有廣泛應用背景（略） 10由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)。 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函數m(i,j)是由函數m(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的并集中

11、。易知，(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中的其他跳躍點均為pi中的跳躍點。由此可見，在遞歸地由表pi+1計算表pi時，可先由pi+1計算出qi+1，然后合并表pi+1和表qi+1，并清除其中的受控跳躍點得到表pi。 13n=5，c=10，w=2

12、，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,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。 14上述算法的主要計算量在于計算跳躍點集pi(1in)。由于qi+1=pi+1(wi，vi)，故計算qi+1需要O(|pi+1|)計算時間。合并pi+1和qi+1并清除受控跳躍點也需要O(|pi+