第六章動態(tài)規(guī)劃

1、第六章 動態(tài)規(guī)劃6.1 動態(tài)規(guī)劃的思想方法6.1.1 動態(tài)規(guī)劃的最優(yōu)決策原理活動過程劃分為若干個階段，每一階段的決策，依賴于前一階段的狀態(tài)，由決策所采取的動作，使狀態(tài)發(fā)生轉(zhuǎn)移，成為下一階段的決策依據(jù)。圖6.1 動態(tài)規(guī)劃的決策過程最優(yōu)性原理：無論過程的初始狀態(tài)和初始決策是什么，其余決策都必須相對于初始決策所產(chǎn)生的狀態(tài)，構(gòu)成一個最優(yōu)決策序列。令最優(yōu)狀態(tài)為，由此倒推：最優(yōu)決策序列，狀態(tài)轉(zhuǎn)移序列：賴以決策的策略或目標，稱為動態(tài)規(guī)劃函數(shù)。整個決策過程，可以遞歸地進行，或用循環(huán)迭代的方法進行。動態(tài)規(guī)劃函數(shù)可以遞歸地定義，也可以用遞推公式來表達。最優(yōu)決策是在最后階段形成的，然后向前倒推，直到初始階段；而決策

2、的具體結(jié)果及所產(chǎn)生的狀態(tài)轉(zhuǎn)移，卻是由初始階段開始進行計算的，然后向后遞歸或迭代，直到最終結(jié)果。6.1.2 動態(tài)規(guī)劃實例、貨郎擔問題例6.1 貨郎擔問題。在有向賦權(quán)圖中，尋找路徑最短的哈密爾頓回路問題。一、解貨郎擔問題的過程令：從頂點出發(fā)，經(jīng)中各頂點一次，最終回到頂點的最短路徑的長度，開始時，。動態(tài)規(guī)劃函數(shù)：（6.1.1）（6.1.2）4個城市的費用矩陣是：根據(jù)（6.1.1）式，由城市1出發(fā)，經(jīng)城市2,3,4然后返回1的最短路徑長度為：它必須依據(jù)的計算結(jié)果：這一階段的決策，又必須依據(jù)下面的計算結(jié)果：再向前倒推，有：有了這些結(jié)果，再向后計算，有：路徑順序是：2,3,4,1路徑順序是：3,2,4,1

3、路徑順序是：4,3,2,1最后：路徑順序是：1,2,3,4,1圖6.2 貨郎擔問題求解過程示意圖二、復雜性分析令是計算從頂點出發(fā)，返回頂點所需計算的形式為的個數(shù)。開始計算時，集合中有個城市。以后，在計算時，集合的城市數(shù)目，在不同的決策階段，分別為,0。在整個計算中，需要計算大小為的不同城市集合的個數(shù)為，。因此，總個數(shù)為：當集合中的城市個數(shù)為時，為計算，需次加法， 次比較。從城市出發(fā)，經(jīng)其它城市再回到，總的運算時間為：由二項式定理：令；可得：則用動態(tài)規(guī)劃方法求解貨郎擔問題，總的花費為：6.2 多段圖的最短路徑問題6.2.1 多段圖的決策過程定義6.1 有向連通賦權(quán)圖，頂點集合劃分成個不相交的子集

4、，使得中的任一邊，必有，。稱為多段圖。令，稱為源點，為收點。多段圖的最短路徑問題，是求從源點到達收點的最小花費的通路一、頂點編號：根據(jù)多段圖的個不相交的子集，把多段圖劃分為段，每一段包含頂點的一個子集。把頂點集合中的所有頂點，按照段的順序進行編號。子集中的頂點互不鄰接，它們之間的相互順序無關(guān)緊要。頂點個數(shù)為，頂點的編號為0，則收點的編號為，對中的任何一條邊，頂點的編號小于頂點的編號。二、決策過程數(shù)組元素：存放頂點到達收點的最小花費數(shù)組元素：存放頂點到達收點的最小花費通路上的前方頂點編號數(shù)組：存放從源點出發(fā)，到達收點的最短通路上的頂點編號第一階段，確定第段的所有頂點到達收點的花費最小的通路。第二

5、階段，用第一階段的信息，確定第段的所有頂點到達收點的花費最小的通路。如此依次進行，直到最后確定源點到達收點的花費最小的通路。最后，從源點的信息中，確定它的前方頂點編號，從的信息中，確定的前方頂點編號，如此遞推，直到收點。動態(tài)規(guī)劃函數(shù)：（6.2.1）（6.2.2）三、步驟：(n為頂點個數(shù))1. 對所有的，把初始化為最大值，初始化為-1；初始化為0；2. 令；3. 根據(jù)（6.2.1）式和（6.2.2）式計算和；4. ，若，轉(zhuǎn)3；否則，轉(zhuǎn)5；5. 令，；6. 如果，算法結(jié)束；否則，轉(zhuǎn)7；7. ，；轉(zhuǎn)6；例6.2 求解圖6.3所示的最短路徑問題。圖6.3 動態(tài)規(guī)劃方法求解多段圖的例子(i表示頂點編號)

6、： ： ： ： ： ： ： ： ： 最后，得到最短的路徑為0，2，3，5，8，9，費用是15。6.2.2 多段圖動態(tài)規(guī)劃算法的實現(xiàn)struct NODE /* 鄰接表結(jié)點的數(shù)據(jù)結(jié)構(gòu) */ intv_num;/* 鄰接頂點的編號 */Typelen;/* 鄰接頂點與該頂點的費用 */struct NODE *next;/* 下一個鄰接頂點 */;struct NODE noden;/* 多段圖鄰接表頭結(jié)點 */Typecostn;/* 在階段決策中,各個頂點到收點的最小費用 */introuten;/* 從源點到收點的最短路徑上的頂點編號 */intpathn;/* 在階段決策中,各個頂點到收點

7、的最短路徑上的前方頂點編號 */算法6.1 多段圖的動態(tài)規(guī)劃算法輸入：多段圖鄰接表頭結(jié)點node,頂點個數(shù)n輸出：最短路徑費用,最短路徑上的頂點編號順序route 1. template <class Type> 2. #define MAX_TYPE max_value_of_Type 3. #define ZERO_TYPE zero_value_of_Type4. Type fgraph(struct NODE node,int route,int n)5. 6. int i;7. struct NODE *pnode;8. int *path = new intn;9. T

8、ype min_cost,*cost = new Typen;10. for (i=0;i<n;i+) 11. costi = MAX_TYPE; pathi = -1; roueti = 0;12. 13. costn-1 = ZERO_TYPE;14. for (i=n-2;i>=0;i-) 15. pnode = nodei->next;16. while (pnode!=NULL) 17. if (pnode->len+costpnode->v_num<costi) 18. costi = pnode->len + costpnode->

9、v_num;19. pathi = pnode->v_num;20. 21. pnode = pnode->next;22. 23. 24. i = 0;25. while (routei!=n-1)&&(pathi!=-1) 26. i+;27. routei = pathroutei-1;28. 29. min_cost = cost0;30. delete path; deleye cost;31. return min_cost; 32. 時間復雜性：1013行的初始化，花費時間。1423行局部決策，假定圖的邊數(shù)為，則花費時間為。2428行形成最優(yōu)決策序列，

10、若多段圖分為段，花費時間?？臻g復雜性是。6.3 資源分配問題資源總數(shù)為，工程個數(shù)為。給每項工程投入的資源不同，所獲得的利潤也不同。要求把總數(shù)為的資源，分配給個工程，以獲得最大利潤的分配方案。6.3.1 資源分配的決策過程一、目標函數(shù)和約束方程資源劃分為個相等的部分，每份資源為，為整數(shù)。利潤函數(shù)： 份資源分配給第個工程所得到的利潤，已知分配份資源給所有工程，所得到的利潤總額為：使最大的分配方案： 二、決策過程各個工程按順序編號，階段劃分： ：把份資源分配給前個工程時，所得到的最大利潤，：使最大時，分配給第個工程的資源份額。在第一階段，只把份資源分配給第一個工程，有：（6.3.1）在第二階段，只把

11、份資源分配給前面兩個工程，有：一般的，在第階段，把份資源分配給前面?zhèn)€工程，有：（6.3.2）令第階段的最大利潤為，則：（6.3.3）設是使達最大時，分配給前面?zhèn)€工程的資源份額，則：（6.3.4）在每個階段，把所得到的所有局部決策值,保存起來。最后，在第階段結(jié)束之后，令全局的最大利潤為，則：（6.3.5）在全局最大利潤下，所分配工程項目的最大編號（即所分配工程項目的最大數(shù)目）為，則：（6.3.6）分配給前面?zhèn)€工程的最優(yōu)份額為：（6.3.7）分配給第個工程的最優(yōu)份額為：分配給其余個工程的剩余的最優(yōu)份額為：由此回溯，得到分配給前面各個工程的最優(yōu)份額的遞推關(guān)系式：（6.3.8）由上面的決策過程，可以把

12、求解資源分配問題，劃分為下面四個步驟：1. 按(6.3.1)(6.3.2)式，對各個階段，各個不同份額的資源，計算及；2. 按(6.3.3)(6.3.4)式，計算各個階段的最大利潤，及獲得此最大利潤的分配份額；3. 按(6.3.5)(6.3.6) (6.3.7)式，計算全局的最大利潤，總的最優(yōu)分配份額,及編號最大的工程項目；4. 按(6.3.8)式遞推計算各個工程的最優(yōu)分配份額。例6.3 有8個份額的資源，分配給3個工程，其利潤函數(shù)如下： x0123456780426404550515253051540607073747505154080909598100求資源的最優(yōu)分配方案。解 在第一階段，

13、只把資源的份額分配給第一個工程，由(6.3.1)式，有： x0123456780426404550515253012345678其次，把資源的份額分配給前面兩個個工程，當，顯然有：，；當，由(6.3.2)式有：當，有：類似地計算時的及的值，有：x012345678052640607086100110010045445同樣，計算出及的值，有：x0123456780526408090106120140010045444第二步，按(6.3.3)(6.3.4)式，求各個階段的最大利潤，及在此利潤下的分配份額，有：第三步，按(6.3.5)(6.3.6) (6.3.7)式，計算全局的最大利潤，最大的工程數(shù)

14、目、及總的最優(yōu)分配份額，有：第四步，按(6.3.8)式計算各個工程的最優(yōu)分配份額，有：最后的決策結(jié)果：分配給第2、3工程各4個份額，可得最大利潤140。6.3.2 資源分配算法的實現(xiàn)數(shù)據(jù)結(jié)構(gòu)。下面的數(shù)據(jù)用于算法的輸入：intm;/* 可分配的資源份額 */intn;/* 工程項目個數(shù) */TypeGnm+1;/* 各項工程分配不同份額資源時可得到的利潤表 */下面的數(shù)據(jù)用于算法的輸出：Typeoptg;/* 最優(yōu)分配時所得到的總利潤 */intoptqn;/* 最優(yōu)分配時各項工程所得到的份額 */下面的數(shù)據(jù)用于算法的工作單元：Typefnm+1;/* 前i項工程分配不同份額資源時可得到的最大利

15、潤 */intdnm+1;/* 使fix最大時,第i項工程分配的份額 */Typegn;/* 只分配給前i項工程時,可得到的最大利潤 */intqn;/* 只分配給前i項工程時,第i項工程最優(yōu)分配份額 */intoptx;/* 最優(yōu)分配時的資源最優(yōu)分配份額 */intk;/* 最優(yōu)分配時的工程項目的最大編號 */算法6.2 資源分配算法輸入：工程項目個數(shù)n, 可分配的資源份額m, 各項工程分配不同份額資源時可得到的利潤表G輸出：最優(yōu)分配時所得到的總利潤optg, 最優(yōu)分配時各項工程所得到的份額optq 1. template <class Type> 2. Type allot_r

16、es(int n,int m,Type G,int optq) 3. 4. int optx,k,i,j,s; 5. int *q = new intn;/* 分配工作單元 */ 6. int (*d)m+1 = new intnm+1; 7. Type (*f)m+1 = new Typenm+1; 8. Type *g = new Typen; 9. for (j=0;j<=m;j+) /* 第一個工程的份額利潤表 */10. f0j = G0j; d0j = j;11. 12. for (i=1;i<n;i+) /* 前i個工程的份額利潤表*/13. fi0 = Gi0 +

17、fi-10;14. di0 = 0;15. for (j=1;j<=m;j+) 16. fij = fi0; dij = 0;17. for (s=0;s<=j;s+) 18. if (fij<Gis+fi-1j-s) 19. fij = Gis + fi-1j-s;20. dij = s; 21. 22. 23. 24. 25. for (i=0;i<n;i+) /* 前i個工程的最大利潤和最優(yōu)分配份額 */24. gi = fi0; qi = 0;25. for (j=1;j<=m;j+) 26. if (gi<fij) 27. gi = fij; qi

18、 = j;28. 29. 30. 31. optg = g0; optx = q0; k = 0;32. for (i=1;i<n;i+) /* 全局的最大利潤和最優(yōu)分配份額 */33. if (optg<gi) /* 以及最大數(shù)目的工程項目及其編號*/34. optg = gi; optx = qi; k = i;35. 36. 37. if (k<n-1) /* 最大編號之后的工程項目不分配份額 */38. for (i=k+1;i<n;i+)39. optqi = 0;40. for (i=k;i>=0;i-) /* 給最大編號之前的工程項目分配份額 */4

19、1. optqi = dioptx;42. optx = optx optqi;43. 44. delete q; delete d; /* 釋放工作單元 */45. delete f; delete g; 46. return optg;/* 返回最大利潤 */47. 時間復雜性：911行執(zhí)行一個循環(huán)，花費時間；1224行執(zhí)行一個三重循環(huán)，花費；2530行花費時間；3136行花費時間；空間復雜性是。6.4 設備更新問題設備每年的運轉(zhuǎn)都可為公司創(chuàng)造利潤收入，設備的性能隨使用年限的增加而變壞，導致收入減少，維修費增加，利潤下降。設備的更新，需付出一筆經(jīng)費，但可增加利潤收入。設備的更新問題是確定設

20、備的最優(yōu)更新策略，使得在一個確定期限里，為公司創(chuàng)造最大的利潤。6.4.1 設備更新問題的決策過程設備更新問題的有關(guān)數(shù)據(jù)如表6.1所示。I = 0列，表明現(xiàn)有設備的有關(guān)數(shù)據(jù)；I = 1列，表示第一年購買的設備的有關(guān)數(shù)據(jù) 其余類推；使用年限：第0列：當年的有關(guān)數(shù)據(jù)，第一列：使用一年后的有關(guān)數(shù)據(jù)，其余類推；利潤、維修費用、更新費用：在第年購買的設備，使用了年后，可以創(chuàng)造的利潤、必須付出的維修費用、以及進行更新時需要付出的費用。表6.1 設備更新的有關(guān)數(shù)據(jù)購買時間I = 0I = 1I = 2I = 3I = 4I = 5使用年限2 3 4 5 6 0 1 2 3 4 0 1 2 30 1 2 0 1

21、0利 潤13 12 11 10 9 16 15 14 13 1217 16 15 14 18 17 1619 1820維修費用2 3 4 4 5 1 1 2 2 31 1 2 21 1 21 11更新費用25 26 27 28 2920 22 24 25 26 20 22 24 2520 22 2421 2221變量和函數(shù)：第年購買的設備使用了年后，在第年所創(chuàng)造的利潤；第年購買的設備使用了年后，在第年所付出的維修費用；第年購買的設備使用了年后，在第年進行更新的費用；使用了年后的設備，第年被更新，在第年及其以后的年份所創(chuàng)造的總利潤（在今后的年份里，設備還可能被更新）；使用了年后的設備，第年繼續(xù)使

22、用，在第年及其以后的年份所創(chuàng)造的總利潤（在今后的年份里，設備還可能被更新）；使用了年后的設備，在第年及其以后的年份里，所創(chuàng)造的總利潤；對使用了年后的設備，在第年所作出的更新設備、或保留繼續(xù)使用的決策；以現(xiàn)有設備為基礎，在第年作出的更新設備、或保留繼續(xù)使用的最優(yōu)決策；現(xiàn)有設備已經(jīng)使用了年。則設備更新問題表示為在今后年里，使得最大的最優(yōu)決策序列，。對使用了年后的設備，第年決定更新，則利潤函數(shù)如下：（6.4.1）如果第年決定保留繼續(xù)使用，則有利潤函數(shù)如下：（6.4.2）于是，可以定義如下的規(guī)劃函數(shù)：（6.4.3）（6.4.4）假定，所要決策的年限為年，對所有的，令（6.4.5）階段劃分：把年劃分為個

23、階段。第階段，設備的使用年限為。計算，確定；第階段，設備的使用年限為。計算,確定；依此類推，第一階段，設備的使用年限，只能為，計算，并確定。第一年的決策由作出，如果是買，則第二年的決策，應由作出；如果是留，則應由作出。決策序列的遞推公式：（6.4.6）例6.4 設備已使用2年，按照表6.1的數(shù)據(jù)，確定5年內(nèi)的設備更新決策，及在此決策下的最大利潤。假定，用數(shù)組和分別存放和的值，按照上面所述步驟，計算和，得到下面的表。表6.2 例6.4中各年限可得利潤及決策f1D=41 rf21=46 rf21+D=30 bf31=40 rf32=32 rf32+D=20 bf41=30 rf42=25 rf43

24、=20 rf43+D=10 rf51=17 rf52=14 rf53=12 rf54=9 rf54+D=4 r5年中的更新策略為留、買、留、留、留，5年內(nèi)可得總利潤41。決策過程如圖6.4所示，其中，粗線表示最優(yōu)決策。圖6.4 設備更新的決策過程6.4.2 設備更新算法的實現(xiàn)數(shù)據(jù)結(jié)構(gòu)。下面的數(shù)據(jù)用于算法的輸入：intn;/* 決策年限 */intD;/* 設備當前的使用年限 */Typernn+D;/* 使用了年后的設備,在第年所創(chuàng)造的利潤 */Typemnn+D;/* 使用了年后的設備,在第年的維修費用利潤 */Typeunn+D;/* 使用了年后的設備,在第年的更新費用 */下面的數(shù)據(jù)用于

25、算法的輸出：BOOLpn;/* 每年的最優(yōu)決策 */下面的數(shù)據(jù)用于算法的工作單元：Typefnn;/* 使用了年后的設備,在第年及其以后所創(chuàng)造的利潤 */Boolxnn;/* 使用了年后的設備,在第年的更新決策 */算法描述：算法6.3 設備更新算法輸入：決策年限n,設備已使用年限D(zhuǎn),設備利潤表r,維修費用表m,更新費用表u輸出：最優(yōu)利潤optg,及最優(yōu)更新方案p 1. template <class Type> 2. Type update_dev(int n,int D,Type r,Type m,Type u,BOOL p) 3. 4. int i,j,k;/* 分配工作空間

26、 */ 5. Type optg,rem; 6. Type (*f)n+1 = new Typen+2n+1; 7. BOOL (*x)n+1 = new BOOLn+1n+1; 8. for (i=1;i<=n;i+)/* 第n+1年的利潤初始化為0 */ 9. fn+1i = 0;10. for (i=n;i>0;i-) /*第1年第n年各種設備使用年限的利潤*/11. for (j=1;j<=i;j+) 12. if (i>j) /* 買,可得到的利潤 */ 13. fij = ri0 mi0 ui-jj + fi+11;14. else15. fij = ri0

27、 mi0 u0j-1+D + fi+11; 16. xij = TRUE;17. if (i>j) /* 留,可得到的利潤 */18. rem = ri-jj mi-jj + fi+1j+1;19. else20. rem = r0j-1+D m0j-1+D +fi+1j+1;21. if (fij<rem) /* 決策,取二者中只最大者 */22. fij = rem; xij = FALSE;23. 24. 25. 26. j = 1;/* 全局的更新決策 */27. for (i=1;i<=n;i+) 28. pi = xij;/* 從第一年的決策開始 */29. if

28、 (pi) /* 當年的決策：更新 */30. j = 1;/* 下一年決策時,設備年限為1年 */31. else 32. j = j + 1;/*否則,下一年決策時,設備年限增1 */33. 34. optg = f11;35. delete f; delete x;/* 釋放工作空間 */36. return optg;/* 返回最優(yōu)更新時可得到的利潤 */37. 時間復雜性：89行需要時間。1026行，內(nèi)循環(huán)的循體共執(zhí)行次，花費時間。2633行花費時間?？臻g復雜性是。6.5 最長公共子序列問題一、字符子序列上的字符序列，存在上的另一字符序列，對所有的，有，其中， ，是的下標遞增序列，稱

29、是的子序列。例：， 是的長度為3的子序列。子序列中的字符，相應于的下標是1,5,7。是的長度為5的子序列。子序列中的字符，相應于的下標是1,3,4,6,7。子序列有多個。例：和，長度為3的公共子序列，長度為4的公共子序列。長度為6的最長公共子序列。二、最長公共子序列問題：給定序列和，尋找和的一個公共子序列，使得它是和的最長公共子序列。6.5.1 最長公共子序列的搜索過程一、最長公共子序列的性質(zhì)，。記為序列中最前面連續(xù)個字符的子序列，記為序列中最前面連續(xù)個字符的子序列。有如下性質(zhì)：1. 若，是和的長度為的最長公共子序列。有，且序列是和的長度為的最長公共子序列；2. 若,且，則是和的長度為的最長公

30、共子序列；3. 若,且，則是和的長度為的最長公共子序列；二、最長公共子序列的的搜索過程1、最長公共子序列的長度記為和的最長公共子序列的長度，則為和的最長公共子序列的長度。有：（6.5.1）（6.5.2）第一階段，計算和的最長公共子序列的長度。第二階段，計算和的最長公共子序列的長度。第階段，計算和的最長公共子序列的長度。第階段的便是序列和的最長公共子序列的長度。2、最長公共子序列的獲取二維狀態(tài)字數(shù)組， 若 （6.5.3）若 ，且 （6.5.4）若 ，且 （6.5.5）設，是和的長度為的最長公共子序列。搜索過程如下：若：。根據(jù)性質(zhì)1，下一個搜索方向是；若：，且。由性質(zhì)2，下一個搜索方向是；若：，且

31、。由性質(zhì)3，下一個搜索方向是。得到遞推關(guān)系：若 則，（6.5.6）若 則（6.6.7）若 則（6.7.8）從，開始搜索，直到或結(jié)束，即可得到和的最長公共子序列。例6.5 求，的最長公共子序列。解 用兩個的表，來分別存放和狀態(tài)。的計算結(jié)果如圖6.5所示。由圖中看到，最長公共子序列的長度為8。圖6.5 最長公共子序列長度的計算例子圖6.6表示用搜索公共子序列的過程。公共子序列是。圖6.6 最長公共子序列字符的搜索過程6.4.2 最長公共子序列算法的實現(xiàn)數(shù)據(jù)結(jié)構(gòu)。下面的數(shù)據(jù)用于算法的輸入和輸出：charAn+1,Bm+1;/* 序列A和B */char Cn+1;/* 序列A和B的公共子序列 */下

32、面的數(shù)據(jù)用于算法的工作單元：int Ln+1m+1;/* 搜索過程中的子序列長度 */int sn+1m+1;/* 搜索過程中的子序列狀態(tài) */為了簡便起見，字符序列及其公共子序列，均從下標為1的數(shù)組元素開始存放。算法6.4 求最長公共子序列算法輸入：字符序列A和B,序列A的長度n,序列B的長度m輸出：最長公共子序列C,及其長度len 1. int lcs(char A,char B,char C,int n,int m) 2. 3. int i,j,k,len;/* 分配工作空間 */ 4. int (*L)m+1 = new intn+1m+1; 5. int (*s)m+1 = new

33、intn+1m+1; 6. for (i=0;i<=n;i+)/* 初始化第0列 */ 7. Li0 = 0; 8. for (i=0;i<=m;i+)/* 初始化第0行 */ 9. L0i = 0;10. for (i=1;i<=n;i+) /* 計算長度及狀態(tài)字 */11. for (j=1;j<=m;j+) 12. if (Ai=Bj) 13. Lij = Li-1j-1;14. sij = 1;15. 16. else if (Li-1j>=Lij-1) 17. Lij = Li-1j;18. sij = 2;19. 20. else 21. Lij =

34、Lij-1;22. sij = 3;23. 24. 25. 26. i = n; j = m; k = len = Lij;27. while (i!=0)&&(j!=0) /* 搜索最長公共子序列字符 */28. switch (sij) 29. case 1: Ck = Ai; k-;30. j-; 31. case 2: i-; break;32. case 3: j-; break; 33. 34. 35. delete L; delete s;/* 釋放工作空間 */36. return len;/* 返回最長公共子序列長度 */37. 時間復雜性:第67行花費時間；第89行花費時間；第1025行花費時間；第2634行花費；空間復雜性是。6.6 0/1背包問題6.6.1 0/1背包問題的求解過程一、動態(tài)規(guī)劃函數(shù)：物體被裝入背包的情況，。約束方程和目標函數(shù)：解向量。背包的載重量： ：前個物體中，能裝入載重量為的背包中的物體的最大價值，。動態(tài)規(guī)劃函數(shù)：（6.6.1）（6.6.2）二、求解過程 1、決策階段第一階段，只裝入一個物體，確定在各種不同載重量的背包下，能夠得到的最大價值；第二階段，裝入前兩個物體，確定在各種不同載重量的背包下，能夠得到的最大價值；依此類推，直到第個階段。最后，便是在載重量為的背包下