第7章 動(dòng)態(tài)規(guī)劃PPT

1、算法設(shè)計(jì)與分析,動(dòng)態(tài)規(guī)劃,動(dòng)態(tài)規(guī)劃,主要內(nèi)容： 介紹動(dòng)態(tài)規(guī)劃的基本原理，動(dòng)態(tài)規(guī)劃算法設(shè)計(jì)的基本方法和應(yīng)用實(shí)例。,動(dòng)態(tài)規(guī)劃,一. 引言 1. 關(guān)于動(dòng)態(tài)規(guī)劃 動(dòng)態(tài)規(guī)劃（dynamic programming）是一種通用的算法設(shè)計(jì)技術(shù)，是在20世紀(jì)50年代由美國(guó)數(shù)學(xué)家Richard Bellman發(fā)明的。 應(yīng)用分治法時(shí)，問(wèn)題被分解成互不相交得子問(wèn)題。但有許多問(wèn)題，分解成的子問(wèn)題是互相重疊的，此時(shí)分治法不適用，而應(yīng)用動(dòng)態(tài)規(guī)劃，重疊的子問(wèn)題只解一次。 例：求Fibonacci數(shù)列（例7.1） 動(dòng)態(tài)規(guī)劃常用于解最優(yōu)化問(wèn)題。,斐波納契數(shù)列F(n),遞歸 vs 動(dòng)態(tài)規(guī)劃,遞歸版本: F(n) 1if n=0

2、or n=1 then 2return 1 3else 4return F(n-1) + F(n-2),動(dòng)態(tài)規(guī)劃: F(n) 1A0 = A1 1 2for i 2 to n do 3Ai Ai-1 + Ai-2 4return An,太慢!,有效率! 算法復(fù)雜度是 O(n),方法概要,構(gòu)造一個(gè)公式，它表示一個(gè)問(wèn)題的解是與它的子問(wèn)題的 解相關(guān)的公式.E.g. F(n) = F(n-1) + F(n-2). 為這些子問(wèn)題做索引 ，以便它們能夠在表中更好的存儲(chǔ)與檢索 (i.e., 數(shù)組array【】) 以自底向上的方法來(lái)填寫這表格; 首先填寫最小子問(wèn)題的解. 這就保證了當(dāng)我們解決一個(gè)特殊的子問(wèn)題時(shí)

3、, 可以利用比它更小的所有可利用的 子問(wèn)題的解.,由于歷史原因, 我們稱這種方法為： 動(dòng)態(tài)規(guī)劃. 在上世紀(jì)40年代末 (計(jì)算機(jī)普及很少時(shí)),這些規(guī)劃設(shè)計(jì)是與”列表“方法相關(guān)的.,動(dòng)態(tài)規(guī)劃,一. 引言 2. 最優(yōu)化問(wèn)題 最優(yōu)化問(wèn)題：給定若干個(gè)約束條件和一個(gè)目標(biāo)函數(shù)， 在某指定集合中求滿足所有約束條件的且使得目標(biāo)函數(shù)值達(dá)最大或最小的元素和相應(yīng)的目標(biāo)函數(shù)值。,動(dòng)態(tài)規(guī)劃,一. 引言 2. 最優(yōu)化問(wèn)題 有關(guān)術(shù)語(yǔ)： 可行解：指定集合中滿足所有約束條件的元素。 （不一定唯一） 最優(yōu)解：使目標(biāo)函數(shù)值取最大或最小的可行解。 （不一定唯一） 最優(yōu)值：在最優(yōu)解處的目標(biāo)函數(shù)值。 （唯一） 最優(yōu)化問(wèn)題就是求問(wèn)題的最優(yōu)值

4、和最優(yōu)解（或之一）。 例子：最短路徑問(wèn)題 (最短路徑問(wèn)題),動(dòng)態(tài)規(guī)劃,一. 引言 2. 最優(yōu)化問(wèn)題 數(shù)學(xué)規(guī)劃： 數(shù)學(xué)規(guī)劃是一類應(yīng)用十分廣泛的最優(yōu)化問(wèn)題。 數(shù)學(xué)模型： z=min g(x1, x2, xn) g為目標(biāo)函數(shù) fj(x1, x2, xn)=0 (或=0或=0) 約束條件 , i=1, 2, , n, j=1, 2, , m,動(dòng)態(tài)規(guī)劃,一. 引言 2. 最優(yōu)化問(wèn)題 數(shù)學(xué)規(guī)劃： 例子：0/1背包問(wèn)題 ：0/1背包問(wèn)題 z=max v1x1+ v2x2+ vnxn s1x1+ s2x2+ snxn=C xi=0或1, i=1, 2, , n,動(dòng)態(tài)規(guī)劃,一. 引言 3. 一個(gè)例子：最短路徑問(wèn)

5、題 問(wèn)題描述：給定一個(gè)無(wú)回路的有向網(wǎng)，指定其中一個(gè)頂點(diǎn)為起點(diǎn)，一個(gè)頂點(diǎn)為終點(diǎn)，求起點(diǎn)到終點(diǎn)的最短路徑。 路徑長(zhǎng)度=路徑上所有邊的權(quán)值之和,動(dòng)態(tài)規(guī)劃,3. 一個(gè)例子：最短路徑問(wèn)題 圖例： 返回 返回 返回 返回 返回,動(dòng)態(tài)規(guī)劃,一. 引言 3. 一個(gè)例子：最短路徑問(wèn)題 蠻力方法（枚舉法）：求出從起點(diǎn)到終點(diǎn)的每一條路徑進(jìn)行比較。 上例中從起點(diǎn)1到終點(diǎn)10共有14條路徑。圖例 動(dòng)態(tài)規(guī)劃方法： 性質(zhì)：從起點(diǎn)到終點(diǎn)的最短路徑包含了該路徑上各點(diǎn)到終點(diǎn)的最短路徑。 例如，上例的最短路徑是146910，則其中6910必為頂點(diǎn)6到頂點(diǎn)10的最短路徑。,動(dòng)態(tài)規(guī)劃,一. 引言 3. 一個(gè)例子：最短路徑問(wèn)題 遞歸關(guān)系

6、：設(shè)v為圖中一個(gè)頂點(diǎn)，v1, v2, vm為v的直接后繼，cost(v)表示v到終點(diǎn)的最短路徑長(zhǎng)度，cu, w表示邊上的權(quán)，t為終點(diǎn)，則cost滿足如下遞歸公式： 圖例,兩點(diǎn)之間的最短路徑問(wèn)題,求從某個(gè)源點(diǎn)到其余各點(diǎn)的最短路徑 (Dijkstra算法) 每一對(duì)頂點(diǎn)之間的最短路徑(Floyd算法),單源最短路徑,概念：從一個(gè)確定的頂點(diǎn)v到其余頂點(diǎn)的最短路徑問(wèn)題.實(shí)例： 從V1到V6有四條不同路徑： ，長(zhǎng)度：21（最短路徑） 長(zhǎng)度：32 長(zhǎng)度：49 2長(zhǎng)度：22,求從源點(diǎn)到其余各點(diǎn)的最短路徑的算法的基本思想:,依最短路徑的長(zhǎng)度遞增的次序求得各條路徑,源點(diǎn),v1,其中，從源點(diǎn)到頂點(diǎn)v的最短路徑是所有

7、最短路徑中長(zhǎng)度最短者。,v2,其余最短路徑的特點(diǎn)：,再下一條路徑長(zhǎng)度次短的最短路徑的特點(diǎn):,它可能有三種情況：或者是直接從源點(diǎn)到該點(diǎn)(只含一條弧)； 或者是從源點(diǎn)經(jīng)過(guò)頂點(diǎn)v1，再到達(dá)該頂點(diǎn)(由兩條弧組成)；或者是從源點(diǎn)經(jīng)過(guò)頂點(diǎn)v2，再到達(dá)該頂點(diǎn)。,它或者是直接從源點(diǎn)到該點(diǎn)(只含一條弧)； 或者是從源點(diǎn)經(jīng)過(guò)已求得最短路徑的頂點(diǎn)，再到達(dá)該頂點(diǎn)。,求最短路徑的迪杰斯特拉算法：,一般情況下， Distk = 或者 = + 。,設(shè)置輔助數(shù)組Dist，其中每個(gè)分量Distk 表示 當(dāng)前所求得的從源點(diǎn)到其余各頂點(diǎn) k 的最短路徑。,動(dòng)態(tài)規(guī)劃,一. 引言 3. 一個(gè)例子：最短路徑問(wèn)題 最優(yōu)值和最優(yōu)解的計(jì)算（根

8、據(jù)上面的遞歸公式）： 自底向上（迭代）：從終點(diǎn)開(kāi)始。 自頂向下（遞歸）：從起點(diǎn)開(kāi)始。 圖例,動(dòng)態(tài)規(guī)劃,二. 動(dòng)態(tài)規(guī)劃的基本原理 1. 最優(yōu)性原理 最優(yōu)性原理是動(dòng)態(tài)規(guī)劃的理論基礎(chǔ)，是R. Bellman 在1951年針對(duì)解決多階段決策問(wèn)題提出的原理，動(dòng)態(tài)規(guī)劃是使多階段決策過(guò)程最優(yōu)的通用方法。 最優(yōu)性原理：給出一個(gè)最優(yōu)的決策序列，每個(gè)（連續(xù)）子序列自身必須是最優(yōu)的決策序列。（P136） 例：最短路徑問(wèn)題。圖示,動(dòng)態(tài)規(guī)劃,二. 動(dòng)態(tài)規(guī)劃的基本原理 1. 最優(yōu)性原理 最優(yōu)子結(jié)構(gòu)：一個(gè)最優(yōu)化問(wèn)題的最優(yōu)解包含了其子問(wèn)題的最優(yōu)解，稱這樣的問(wèn)題具有最優(yōu)子結(jié)構(gòu)。 具有最優(yōu)子結(jié)構(gòu)的問(wèn)題滿足最優(yōu)性原理。 例：最短路

9、徑問(wèn)題的最優(yōu)子結(jié)構(gòu)。,動(dòng)態(tài)規(guī)劃,二. 動(dòng)態(tài)規(guī)劃的基本原理 2. 適用動(dòng)態(tài)規(guī)劃求解的問(wèn)題的基本要素 (1) 滿足最優(yōu)性原理 對(duì)于最優(yōu)化問(wèn)題可簡(jiǎn)化為具有最優(yōu)子結(jié)構(gòu)。 (2) 具有重疊的子問(wèn)題 重疊的子問(wèn)題是動(dòng)態(tài)規(guī)劃算法提高效率的依據(jù)。,動(dòng)態(tài)規(guī)劃,二. 動(dòng)態(tài)規(guī)劃的基本原理 3. 設(shè)計(jì)動(dòng)態(tài)規(guī)劃算法的步驟 解最優(yōu)化問(wèn)題的步驟： 1) 找出問(wèn)題的最優(yōu)子結(jié)構(gòu)。 分析問(wèn)題的最優(yōu)解（最優(yōu)值）的結(jié)構(gòu)特征。 2) 遞歸地定義最優(yōu)值。 根據(jù)最優(yōu)子結(jié)構(gòu)，確定最優(yōu)值所滿足的遞歸公式。 3) 計(jì)算最優(yōu)值。 根據(jù)最優(yōu)值的遞歸公式，自底向上或自頂向下地計(jì)算 最優(yōu)值。 4) 構(gòu)造最優(yōu)解。 根據(jù)求最優(yōu)值時(shí)得到的最優(yōu)解信息構(gòu)造最優(yōu)解

10、。,動(dòng)態(tài)規(guī)劃,二. 動(dòng)態(tài)規(guī)劃的基本原理 3. 設(shè)計(jì)動(dòng)態(tài)規(guī)劃算法的步驟 解最優(yōu)化問(wèn)題的步驟： 注意：在計(jì)算最優(yōu)值時(shí)應(yīng)保存相應(yīng)的信息： a) 已經(jīng)求出的子問(wèn)題的最優(yōu)值（避免重復(fù)計(jì) 算）。 b) 最優(yōu)解的有關(guān)信息。,動(dòng)態(tài)規(guī)劃,二. 動(dòng)態(tài)規(guī)劃的基本原理 3. 設(shè)計(jì)動(dòng)態(tài)規(guī)劃算法的步驟 解其它問(wèn)題的步驟： 1) 根據(jù)最優(yōu)化原理分析問(wèn)題的解的結(jié)構(gòu)。 2) 遞歸地定義問(wèn)題的解。 3) 計(jì)算問(wèn)題的解。 根據(jù)解的遞歸公式，自底向上或自頂向下地計(jì)算解，計(jì)算過(guò)程中注意保存已經(jīng)求出的子問(wèn)題的解。 例：動(dòng)態(tài)規(guī)劃解最短路徑問(wèn)題 解最短路徑問(wèn)題,動(dòng)態(tài)規(guī)劃,二. 動(dòng)態(tài)規(guī)劃的基本原理 4. 動(dòng)態(tài)規(guī)劃的自底向上和自頂向下算法 自底

11、向上算法（通過(guò)迭代實(shí)現(xiàn)）： 經(jīng)典的動(dòng)態(tài)規(guī)劃方法，適用于所有的子問(wèn)題都需要解的情況。 實(shí)現(xiàn)的關(guān)鍵：根據(jù)遞歸公式正確確定迭代順序（即子問(wèn)題的求解順序）。,動(dòng)態(tài)規(guī)劃,二. 動(dòng)態(tài)規(guī)劃的基本原理 4. 動(dòng)態(tài)規(guī)劃的自底向上和自頂向下算法 自頂向下算法（通過(guò)遞歸實(shí)現(xiàn)）： 基于記憶功能的動(dòng)態(tài)規(guī)劃方法（動(dòng)態(tài)規(guī)劃方法的一種變形），適用于不必解所有的子問(wèn)題的情況。 實(shí)現(xiàn)的關(guān)鍵：對(duì)每個(gè)子問(wèn)題標(biāo)記是否計(jì)算過(guò)，同一子問(wèn)題只在第一次遞歸調(diào)用時(shí)計(jì)算并存儲(chǔ)結(jié)果。,動(dòng)態(tài)規(guī)劃,二. 動(dòng)態(tài)規(guī)劃的基本原理 5. 動(dòng)態(tài)規(guī)劃和分治法 動(dòng)態(tài)規(guī)劃：分解出的子問(wèn)題是重疊的。 分治法：分解出的子問(wèn)題是相互獨(dú)立的。,動(dòng)態(tài)規(guī)劃,三. 動(dòng)態(tài)規(guī)劃算法設(shè)計(jì)

12、示例 1. 最長(zhǎng)公共子序列問(wèn)題 （LCS） (P130) 問(wèn)題描述：給出兩個(gè)長(zhǎng)度分別為n和m的序列A= a1a2an和B=b1b2bm，求A和B的最長(zhǎng)公共子序列。 例：A=abcbdacb B=bdcab 蠻力方法（枚舉法）:枚舉A所有2n個(gè)子序列，對(duì)每個(gè)子序列確定其是否為B的子序列。時(shí)間復(fù)雜性：(m2n) 。,動(dòng)態(tài)規(guī)劃,三. 動(dòng)態(tài)規(guī)劃算法設(shè)計(jì)示例 1. 最長(zhǎng)公共子序列問(wèn)題 （LCS） (P130) 最優(yōu)子結(jié)構(gòu)： (LCS問(wèn)題的最優(yōu)子結(jié)構(gòu)基于以下性質(zhì)) 記Ai= a1a2ai , Bj=b1b2bj，Ck=c1c2ck。 性質(zhì)：設(shè)Ck為Ai和Bj的最長(zhǎng)公共子序列，則 若ai=bj , 則ck=

13、ai=bj且Ck-1為Ai-1和Bj-1的最長(zhǎng) 公共子序列。 2) 若aibj且ckai , 則Ck為Ai-1和Bj的最長(zhǎng)公共子序列。 3) 若aibj且ckbj , 則Ck為Ai和Bj-1的最長(zhǎng)公共子序列。 由上述性質(zhì)可得觀察結(jié)論7.1。（P131）,動(dòng)態(tài)規(guī)劃,三. 動(dòng)態(tài)規(guī)劃算法設(shè)計(jì)示例 1. 最長(zhǎng)公共子序列問(wèn)題 （LCS） 遞歸公式： 令Li, j表示Ai 和Bj 的最長(zhǎng)公共子序列的長(zhǎng)度，則 原問(wèn)題的最優(yōu)值為L(zhǎng)n, m。,動(dòng)態(tài)規(guī)劃,三. 動(dòng)態(tài)規(guī)劃算法設(shè)計(jì)示例 1. 最長(zhǎng)公共子序列問(wèn)題 （LCS） 求最優(yōu)值的算法：求最長(zhǎng)公共子序列的長(zhǎng)度。 數(shù)據(jù)的存儲(chǔ)： 數(shù)組L0.n, 0.m存儲(chǔ)各個(gè)子問(wèn)題的

14、最優(yōu)值， 數(shù)組H1.n, 1.m存儲(chǔ)最優(yōu)解的有關(guān)信息: 若ai=bj , ,Hi, j=0; （對(duì)應(yīng)情況1） 若aibj且Li-1, j=Li, j-1, Hi, j=1; (對(duì)應(yīng)情況2) 若aibj且Li-1, jLi, j-1, Hi, j=2。 (對(duì)應(yīng)情況3),動(dòng)態(tài)規(guī)劃,三. 動(dòng)態(tài)規(guī)劃算法設(shè)計(jì)示例 1. 最長(zhǎng)公共子序列問(wèn)題 （LCS） 求最優(yōu)值的算法 用自底向上的迭代算法。 迭代順序： 按行序計(jì)算L和H。 算法：算法7.1 LCS,動(dòng)態(tài)規(guī)劃,三. 動(dòng)態(tài)規(guī)劃算法設(shè)計(jì)示例 1. 最長(zhǎng)公共子序列問(wèn)題 （LCS） 構(gòu)造最優(yōu)解：構(gòu)造最長(zhǎng)公共子序列。 構(gòu)造方法：按逆序生成A和B的最長(zhǎng)公共子序列C,

15、C初始化為空序列。從數(shù)組H的最右下元素Hn, m開(kāi)始搜索，直至到達(dá)H的邊界。每一步搜索分三種情況處理： 若Hi, j=0，則在C的前面插入ai ,前進(jìn)到Hi-1, j-1。（C包含ai） 若Hi, j=1，則前進(jìn)到Hi-1, j。（C不包含ai） 若Li, j=2，則前進(jìn)到Hi, j-1。（C不包含bj） 演示：最長(zhǎng)公共子序列.ppt 算法：算法 LCSS,動(dòng)態(tài)規(guī)劃,三. 動(dòng)態(tài)規(guī)劃算法設(shè)計(jì)示例 2. 矩陣鏈乘問(wèn)題 ( P132) 問(wèn)題描述： 給出n個(gè)矩陣M1, M2, , Mn , Mi 為rixri+1階的，i=1, 2, , n，找出使得數(shù)量乘法次數(shù)達(dá)最小的計(jì)算M1M2Mn的乘法順序，該順

16、序稱為計(jì)算M1M2Mn的最優(yōu)順序。 例：不同的乘法順序所需的運(yùn)算量差異很大。,動(dòng)態(tài)規(guī)劃,三. 動(dòng)態(tài)規(guī)劃算法設(shè)計(jì)示例 2. 矩陣鏈乘問(wèn)題 蠻力方法（枚舉法）：枚舉出所有不同的乘法順序，求出每一種順序所需的數(shù)量乘法次數(shù)。 分析：n個(gè)矩陣的鏈乘共有 種不同的乘法順序。 計(jì)算最小的數(shù)量乘法次數(shù)的時(shí)間復(fù)雜性為,動(dòng)態(tài)規(guī)劃,三. 動(dòng)態(tài)規(guī)劃算法設(shè)計(jì)示例 2. 矩陣鏈乘問(wèn)題 最優(yōu)子結(jié)構(gòu)： 記 Mi, j=MiMi+1Mj , i=j 。 設(shè)計(jì)算M1, n的最優(yōu)順序的最后一次矩陣乘法是計(jì)算M1, k-1Mk, n ,1k=n，則該最優(yōu)順序中所包含的計(jì)算M1, k-1 和Mk, n的乘法順序分別是計(jì)算M1, k-1

17、 和Mk, n的最優(yōu)順序。 該問(wèn)題有大量重疊的子問(wèn)題： 圖示：矩陣鏈乘問(wèn)題：子問(wèn)題樹(shù).ppt,動(dòng)態(tài)規(guī)劃,三. 動(dòng)態(tài)規(guī)劃算法設(shè)計(jì)示例 2. 矩陣鏈乘問(wèn)題 遞歸公式： 設(shè)Ci, j, 1=i=j=n, 表示計(jì)算Mi, j的所需的最少數(shù)量乘法次數(shù)，則 計(jì)算M1, n 所需的最少數(shù)量乘法次數(shù)為C1, n。,動(dòng)態(tài)規(guī)劃,三. 動(dòng)態(tài)規(guī)劃算法設(shè)計(jì)示例 2. 矩陣鏈乘問(wèn)題 求最優(yōu)值：求M1, n所需的最少數(shù)量乘法次數(shù)。 信息的存儲(chǔ): 設(shè)置數(shù)組C1.n, 1.n存儲(chǔ)各子問(wèn)題的最優(yōu)值。 設(shè)置數(shù)組S1.n, 1.n存儲(chǔ)最優(yōu)順序信息。 在求Ci, j的同時(shí)記下相應(yīng)的最優(yōu)斷點(diǎn)k于數(shù)組S中，即Si, j滿足： Ci, j=

18、Ci, Si, j-1+CSi, j, j+ rirSi, j rj+1,動(dòng)態(tài)規(guī)劃,三. 動(dòng)態(tài)規(guī)劃算法設(shè)計(jì)示例 2. 矩陣鏈乘問(wèn)題 求最優(yōu)值： 用自底向上的迭代算法。 迭代順序：,例：n=5 d0 d1 d2 d3 d4 C1,1 C1,2 C1,3 C1,4 C1,5 C2,2 C2,3 C2,4 C2,5 C3,3 C3,4 C3,5 C4,4 C4,5 圖7.2 ( P134) C5,5,動(dòng)態(tài)規(guī)劃,三. 動(dòng)態(tài)規(guī)劃算法設(shè)計(jì)示例 2. 矩陣鏈乘問(wèn)題 求最優(yōu)值： 計(jì)算實(shí)例：例7.4 ( P135) 計(jì)算實(shí)例.doc 算法：算法 MATCHAIN1 按最優(yōu)順序計(jì)算矩陣鏈乘積 數(shù)組S1.n, 1.

19、n存儲(chǔ)最優(yōu)順序信息。 Si, j滿足： Ci, j=Ci, Si, j-1+CSi, j, j+ rirSi, j rj+1 算法：算法 MATCHAIN1,動(dòng)態(tài)規(guī)劃,三. 動(dòng)態(tài)規(guī)劃算法設(shè)計(jì)示例 3. 0/1背包問(wèn)題 問(wèn)題描述： 設(shè)有一個(gè)容量為C的背包，n個(gè)物品的集合U=u1, u2, , un，物品uj的體積和價(jià)值分別為sj和vj，C, sj, vj都是正整數(shù)。在U中選擇物品裝入背包，使得裝入背包的物品總價(jià)值最大。設(shè)每種物品或完全裝入或完全不裝入背包。 返回,動(dòng)態(tài)規(guī)劃,三. 動(dòng)態(tài)規(guī)劃算法設(shè)計(jì)示例 3. 0/1背包問(wèn)題 數(shù)學(xué)模型：(為0/1規(guī)劃問(wèn)題) z=max v1x1+ v2x2+ vnx

20、n s1x1+ s2x2+ snxn=C xi=0或1, i=1, 2, , n 解的意義： xi=1表示物品ui裝入背包； xi=0表示物品ui不裝入背包。,動(dòng)態(tài)規(guī)劃,三. 動(dòng)態(tài)規(guī)劃算法設(shè)計(jì)示例 3. 0/1背包問(wèn)題 蠻力方法: 最優(yōu)子結(jié)構(gòu)： 設(shè)(x1, x2, , xn)為背包容量為C，物品集合為u1, u2, , un的0/1背包問(wèn)題的最優(yōu)解，則(x1, x2, , xn-1)為背包容量為C- snxn，物品集合為u1, u2, , un-1的0/1背包問(wèn)題的最優(yōu)解。,動(dòng)態(tài)規(guī)劃,三. 動(dòng)態(tài)規(guī)劃算法設(shè)計(jì)示例 3. 0/1背包問(wèn)題 遞歸公式： 設(shè)Vi, j表示從物品集合u1, u2, ,ui

21、中選擇物品裝入容量為j的背包中所能達(dá)到的最大總價(jià)值，則,原問(wèn)題的最優(yōu)值為Vn, C 。,動(dòng)態(tài)規(guī)劃,三. 動(dòng)態(tài)規(guī)劃算法設(shè)計(jì)示例 3. 0/1背包問(wèn)題 求最優(yōu)值 用自頂向下的遞歸方法（并非所有的子問(wèn)題都需要解）。 數(shù)據(jù)的存儲(chǔ)：數(shù)組V0.n, 0.C存儲(chǔ)各子問(wèn)題的最優(yōu)值，數(shù)組H0.n, 0.C存儲(chǔ)最優(yōu)解的信息： Hi, j=1, 表示求解Vi, j對(duì)應(yīng)的子問(wèn)題時(shí)將物品ui裝入背包。 Hi, j=0, 表示求解Vi, j對(duì)應(yīng)的子問(wèn)題時(shí)物品ui不裝入背包。,動(dòng)態(tài)規(guī)劃,三. 動(dòng)態(tài)規(guī)劃算法設(shè)計(jì)示例 3. 0/1背包問(wèn)題 求最優(yōu)值 初始化Vi, j=-1 , 用以標(biāo)記相應(yīng)的子問(wèn)題未求解過(guò)。 算法：算法 KNAPSACKREC 自底向上的迭代算法: 算法7.4（P139 ，自習(xí)） 注意：該算法未存儲(chǔ)最優(yōu)解的信息，若要進(jìn)一步求最優(yōu)解，則需要加上相應(yīng)步驟。,動(dòng)態(tài)規(guī)劃,三. 動(dòng)態(tài)規(guī)劃算法設(shè)計(jì)示例 3. 0/1背包問(wèn)題 構(gòu)造最優(yōu)解： 利用最優(yōu)解的信息數(shù)組H: Hi, j=1, 表示求解Vi, j對(duì)應(yīng)的子問(wèn)題時(shí)將物品ui裝入背包。 Hi, j=0, 表示求解Vi, j對(duì)應(yīng)的子問(wèn)題時(shí)物品ui不裝入背包。 從最后一個(gè)分量開(kāi)始向前遞推求最優(yōu)解(x1, x2, , xn)。 算法：算法 KNAPSACK_SOLUTION,動(dòng)態(tài)規(guī)劃,三. 動(dòng)態(tài)規(guī)劃算法設(shè)計(jì)示例 3. 0/1背包