動(dòng)態(tài)規(guī)劃-例題眾多-詳細(xì)講解

1、1參與競(jìng)賽的同學(xué)應(yīng)由競(jìng)爭(zhēng)關(guān)系和獨(dú)立關(guān)系參與競(jìng)賽的同學(xué)應(yīng)由競(jìng)爭(zhēng)關(guān)系和獨(dú)立關(guān)系轉(zhuǎn)向合作學(xué)習(xí)的關(guān)系轉(zhuǎn)向合作學(xué)習(xí)的關(guān)系2F(n) = 1if n = 0 or 1F(n-1) + F(n-2)if n 1n012345678910F(n)1123581321345589l斐波納契數(shù)列F(n)3遞歸遞歸 vs 動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃遞歸版本:F(n)1if n=0 or n=1 then2return 13else4return F(n-1) + F(n-2)動(dòng)態(tài)規(guī)劃:F(n)1A0 = A1 12for i 2 to n do3Ai Ai-1 + Ai-24return An太慢太慢!有效率!算法復(fù)雜度是

2、O(n)4方法概要方法概要l構(gòu)造一個(gè)公式，它表示一個(gè)問(wèn)題的解是與它的子問(wèn)題的 解相關(guān)的公式.E.g. F(n) = F(n-1) + F(n-2).l為這些子問(wèn)題做索引 ，以便它們能夠在表中更好的存儲(chǔ)與檢索 (i.e., 數(shù)組array【】)l以自底向上的方法來(lái)填寫這表格; 首先填寫最小子問(wèn)題的解.l這就保證了當(dāng)我們解決一個(gè)特殊的子問(wèn)題時(shí), 可以利用比它更小的所有可利用的 子問(wèn)題的解.由于歷史原因, 我們稱這種方法為：動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃.在上世紀(jì)40年代末 (計(jì)算機(jī)普及很少時(shí)),這些規(guī)劃設(shè)計(jì)是與”列表“方法相關(guān)的.5動(dòng)態(tài)規(guī)劃算法動(dòng)態(tài)規(guī)劃算法l算法思想 將待求解的問(wèn)題分解成若干個(gè)子問(wèn)題，并存儲(chǔ)子問(wèn)

3、題的解而避免計(jì)算重復(fù)的子問(wèn)題，并由子問(wèn)題的解得到原問(wèn)題的解。l動(dòng)態(tài)規(guī)劃算法通常用于求解具有某種最優(yōu)性質(zhì)的問(wèn)題。l動(dòng)態(tài)規(guī)劃算法的基本要素： 最優(yōu)子結(jié)構(gòu)性質(zhì)和重疊子問(wèn)題。6l最優(yōu)子結(jié)構(gòu)性質(zhì)：?jiǎn)栴}的最優(yōu)解包含著它的子問(wèn)題的最優(yōu)解。即不管前面的策略如何，此后的決策必須是基于當(dāng)前狀態(tài)（由上一次決策產(chǎn)生）的最優(yōu)決策。l重疊子問(wèn)題：在用遞歸算法自頂向下解問(wèn)題時(shí)，每次產(chǎn)生的子問(wèn)題并不總是新問(wèn)題，有些問(wèn)題被反復(fù)計(jì)算多次。對(duì)每個(gè)子問(wèn)題只解一次，然后將其解保存起來(lái)，以后再遇到同樣的問(wèn)題時(shí)就可以直接引用，不必重新求解。7動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃解決問(wèn)題的基本特征1. 動(dòng)態(tài)規(guī)劃一般解決最值（最優(yōu)，最大，最小，最長(zhǎng)）問(wèn)題；2.

4、動(dòng)態(tài)規(guī)劃解決的問(wèn)題一般是離散的，可以分解（劃分階段）的；3. 動(dòng)態(tài)規(guī)劃解決的問(wèn)題必須包含最優(yōu)子結(jié)構(gòu)，即可以由（n1）的最優(yōu)推導(dǎo)出n的最優(yōu)8l動(dòng)態(tài)規(guī)劃算法的4個(gè)步驟： 1. 刻畫最優(yōu)解的結(jié)構(gòu)特性. （一維，二維，三維數(shù)組） 2. 遞歸的定義最優(yōu)解. （狀態(tài)轉(zhuǎn)移方程） 3. 以自底向上的方法來(lái)計(jì)算最優(yōu)解. 4. 從計(jì)算得到的解來(lái)構(gòu)造一個(gè)最優(yōu)解.解決問(wèn)題的基本步驟9F(n) = 1if n = 0 or 1F(n-1) + F(n-2)if n 1步驟步驟1：用：用F（n）表示在斐波納契數(shù)列中第）表示在斐波納契數(shù)列中第n個(gè)數(shù)的值；個(gè)數(shù)的值；步驟步驟2：狀態(tài)轉(zhuǎn)移方程：狀態(tài)轉(zhuǎn)移方程：步驟步驟3：以自底向

5、上的方法來(lái)計(jì)算最優(yōu)解：以自底向上的方法來(lái)計(jì)算最優(yōu)解n012345678910F(n)1123581321345589步驟步驟4：在數(shù)組中分析構(gòu)造出問(wèn)題的解；：在數(shù)組中分析構(gòu)造出問(wèn)題的解；10F(n) = 1if n = 0 or 1F(n-1) *nif n 1步驟步驟1：用：用F（n）表示）表示n！的值；！的值；步驟步驟2：狀態(tài)轉(zhuǎn)移方程：狀態(tài)轉(zhuǎn)移方程：步驟步驟3：以自底向上的方法來(lái)計(jì)算最優(yōu)解：以自底向上的方法來(lái)計(jì)算最優(yōu)解n012345678910F(n)11262412072011l 一場(chǎng)演唱會(huì)即將舉行。現(xiàn)有一場(chǎng)演唱會(huì)即將舉行?，F(xiàn)有n個(gè)歌迷排隊(duì)買票，個(gè)歌迷排隊(duì)買票，一個(gè)人買一張，而售票處規(guī)定

6、，一個(gè)人每次最多一個(gè)人買一張，而售票處規(guī)定，一個(gè)人每次最多只能買兩張票。假設(shè)第只能買兩張票。假設(shè)第i位歌迷買一張票需要時(shí)間位歌迷買一張票需要時(shí)間Ti（1in），），隊(duì)伍中相鄰的兩位歌迷（第隊(duì)伍中相鄰的兩位歌迷（第j個(gè)人和個(gè)人和第第j+1個(gè)人）也可以由其中一個(gè)人買兩張票，而另個(gè)人）也可以由其中一個(gè)人買兩張票，而另一位就可以不用排隊(duì)了，則這兩位歌迷買兩張票一位就可以不用排隊(duì)了，則這兩位歌迷買兩張票的時(shí)間變?yōu)榈臅r(shí)間變?yōu)镽j，假如假如Rj fi-1+Ti then 7 fi fi-1+Ti8 return f141問(wèn)題描述問(wèn)題描述 設(shè)有一個(gè)正整數(shù)的序列：設(shè)有一個(gè)正整數(shù)的序列：b1,b2,，bn，對(duì)于下

7、標(biāo)，對(duì)于下標(biāo)i1i2im，若有，若有bi1bi2bim 則稱存在一個(gè)長(zhǎng)度為則稱存在一個(gè)長(zhǎng)度為m的不下降序列。的不下降序列。 例如，下列數(shù)列例如，下列數(shù)列 13 7 9 16 38 24 37 18 44 19 21 22 63 15 對(duì)于下標(biāo)對(duì)于下標(biāo)i1=1，i2=4，i3=5，i4=9，i5=13，滿足，滿足1316384463,則存則存在長(zhǎng)度為在長(zhǎng)度為5的不下降序列。的不下降序列。 但是，我們看到還存在其他的不下降序列但是，我們看到還存在其他的不下降序列: i1=2，i2=3，i3=4，i4=8，i510，i6=11，i7=12，i8=13，滿足：，滿足：79161819212263，則存

8、在長(zhǎng)度，則存在長(zhǎng)度為為8的不下降序列。的不下降序列。 問(wèn)題為：當(dāng)問(wèn)題為：當(dāng)b1,b2,，bn給出之后，求出最長(zhǎng)的不下降序列。給出之后，求出最長(zhǎng)的不下降序列。 步驟步驟1：用：用F（i）表示第）表示第i項(xiàng)到最后一項(xiàng)最長(zhǎng)不下降序列的長(zhǎng)度的值；項(xiàng)到最后一項(xiàng)最長(zhǎng)不下降序列的長(zhǎng)度的值；步驟步驟2：狀態(tài)轉(zhuǎn)移方程；：狀態(tài)轉(zhuǎn)移方程；di表示數(shù)列中第i項(xiàng)的值；步驟步驟3：以自底向上的：以自底向上的方法來(lái)計(jì)算最優(yōu)解方法來(lái)計(jì)算最優(yōu)解 1max , 1 F iiNF j ijnd id j= =+ 15 （vijos1303）某國(guó)為了防御敵國(guó)的導(dǎo)彈襲擊，發(fā)展出一種導(dǎo)彈攔截系統(tǒng)。但是這種導(dǎo)彈攔截系統(tǒng)有一個(gè)缺陷：雖然它的

9、第一發(fā)炮彈能夠到達(dá)任意的高度，但是以后每一發(fā)炮彈都不能高于前一發(fā)的高度。某天，雷達(dá)捕捉到敵國(guó)的導(dǎo)彈來(lái)襲。由于該系統(tǒng)還在試用階段，所以只有一套系統(tǒng)，因此有可能不能攔截所有的導(dǎo)彈。 輸入導(dǎo)彈依次飛來(lái)的高度（雷達(dá)給出的高度數(shù)據(jù)是不大于30000的正整數(shù)），計(jì)算這套系統(tǒng)最多能攔截多少導(dǎo)彈，如果要攔截所有導(dǎo)彈最少要配備多少套這種導(dǎo)彈攔截系統(tǒng)。 樣例： INPUT OUTPUT 389 207 155 300 299 170 158 65 6（最多能攔截的導(dǎo)彈數(shù)） 2（要攔截所有導(dǎo)彈最少要配備的系統(tǒng)數(shù)）16 “低價(jià)購(gòu)買”這條建議是在奶牛股票市場(chǎng)取得成功的一半規(guī)則。要想被認(rèn)為是偉大的投資者，你必須遵循以下的

10、問(wèn)題建議:“低價(jià)購(gòu)買；再低價(jià)購(gòu)買”。每次你購(gòu)買一支股票,你必須用低于你上次購(gòu)買它的價(jià)格購(gòu)買它。買的次數(shù)越多越好!你的目標(biāo)是在遵循以上建議的前提下，求你最多能購(gòu)買股票的次數(shù)。你將被給出一段時(shí)間內(nèi)一支股票每天的出售價(jià)(216范圍內(nèi)的正整數(shù))，你可以選擇在哪些天購(gòu)買這支股票。每次購(gòu)買都必須遵循“低價(jià)購(gòu)買；再低價(jià)購(gòu)買”的原則。寫一個(gè)程序計(jì)算最大購(gòu)買次數(shù)。這里是某支股票的價(jià)格清單：日期 1 2 3 4 5 6 7 8 9 10 11 12價(jià)格 68 69 54 64 68 64 70 67 78 62 98 87最優(yōu)秀的投資者可以購(gòu)買最多4次股票，可行方案中的一種是： 日期 2 5 6 10價(jià)格 69

11、68 64 62輸入輸入第1行: N (1 = N = 5000)，股票發(fā)行天數(shù)第2行: N個(gè)數(shù)，是每天的股票價(jià)格。輸出輸出輸出文件僅一行包含兩個(gè)數(shù):最大購(gòu)買次數(shù)和擁有最大購(gòu)買次數(shù)的方案數(shù)(=231)當(dāng)二種方案“看起來(lái)一樣”時(shí)（就是說(shuō)它們構(gòu)成的價(jià)格隊(duì)列一樣的時(shí)候）,這2種方案被認(rèn)為是相同的。17 N位同學(xué)站成一排，音樂(lè)老師要請(qǐng)其中的(N-K)位同學(xué)出列，使得剩下的K位同學(xué)排成合唱隊(duì)形。 合唱隊(duì)形是指這樣的一種隊(duì)形：設(shè)K位同學(xué)從左到右依次編號(hào)為1，2，K，他們的身高分別為T1，T2，TK， 則他們的身高滿足T1.Ti+1TK(1=i=K)。你的任務(wù)是，已知所有N位同學(xué)的身高，計(jì)算最少需要幾位同學(xué)

12、出列，可以使得剩下的同學(xué)排成合唱隊(duì)形。 輸入的第一行是一個(gè)整數(shù)輸入的第一行是一個(gè)整數(shù)N(2=N=100)，表示同學(xué)的總數(shù)。第一行有，表示同學(xué)的總數(shù)。第一行有n個(gè)整數(shù)，用空格分隔，第個(gè)整數(shù)，用空格分隔，第i個(gè)整數(shù)個(gè)整數(shù)Ti(130=Ti=230)是第是第i位同學(xué)的身高位同學(xué)的身高(厘米厘米)。 輸出包括一行，這一行只包含一個(gè)整數(shù)，就是最少需要幾位同學(xué)出列。輸出包括一行，這一行只包含一個(gè)整數(shù)，就是最少需要幾位同學(xué)出列。 樣例輸入樣例輸入8186 186 150 200 160 130 197 220樣例輸出：樣例輸出：418問(wèn)題描述問(wèn)題描述:如圖，如圖，A 點(diǎn)有一個(gè)過(guò)河卒，需要走到目標(biāo)點(diǎn)有一個(gè)過(guò)河

13、卒，需要走到目標(biāo) B 點(diǎn)。卒行走規(guī)則：點(diǎn)。卒行走規(guī)則：可以向下、或者向右。同時(shí)在棋盤上的任一點(diǎn)有一個(gè)對(duì)方的馬（如可以向下、或者向右。同時(shí)在棋盤上的任一點(diǎn)有一個(gè)對(duì)方的馬（如上圖的上圖的C點(diǎn)），該馬所在的點(diǎn)和所有跳躍一步可達(dá)的點(diǎn)稱為對(duì)方馬點(diǎn)），該馬所在的點(diǎn)和所有跳躍一步可達(dá)的點(diǎn)稱為對(duì)方馬的控制點(diǎn)。例如上圖的控制點(diǎn)。例如上圖 C 點(diǎn)上的馬可以控制點(diǎn)上的馬可以控制 9 個(gè)點(diǎn)（圖中的個(gè)點(diǎn)（圖中的P1，P2 P8 和和 C）。卒不能通過(guò)對(duì)方馬的控制點(diǎn)。）。卒不能通過(guò)對(duì)方馬的控制點(diǎn)。 棋盤用坐標(biāo)表示，A 點(diǎn)（0，0）、B 點(diǎn)（n,m）(n,m 為不超過(guò) 20 的整數(shù)，并由鍵盤輸入)，同樣馬的位置坐標(biāo)是需要給

14、出的（約定: CA，同時(shí)CB）?，F(xiàn)在要求你計(jì)算出卒從 A 點(diǎn)能夠到達(dá) B 點(diǎn)的路徑的條數(shù)。 輸入輸入:鍵盤輸入B點(diǎn)的坐標(biāo)（n,m）以及對(duì)方馬的坐標(biāo)（X,Y）不用盤錯(cuò) 輸出輸出:屏幕輸出一個(gè)整數(shù)（路徑的條數(shù)）。 輸入輸出樣例輸入輸出樣例:輸入：6 6 3 2輸出：1719步驟步驟1：用：用F（X,Y）表示到棋盤上每個(gè)階段）表示到棋盤上每個(gè)階段(X,Y)的路徑的路徑條數(shù)；條數(shù)；步驟步驟2：狀態(tài)轉(zhuǎn)移方程：狀態(tài)轉(zhuǎn)移方程：步驟步驟3：以自底向上的方法來(lái)計(jì)算最優(yōu)解：以自底向上的方法來(lái)計(jì)算最優(yōu)解分析：階段：棋盤上的每個(gè)可走的點(diǎn)； 每個(gè)階段的求解；F（X,Y）= F (X-1,Y)+ F(X, Y-1)其中，

15、其中，F(xiàn)（0,0 )=1 F (0,Y)=1 F (X,0)=120例題六：數(shù)字三角形問(wèn)題例題六：數(shù)字三角形問(wèn)題1問(wèn)題描述 設(shè)有一個(gè)三角形的數(shù)塔，頂點(diǎn)結(jié)點(diǎn)稱為根結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)有一個(gè)整數(shù)數(shù)值。從頂點(diǎn)出發(fā)，可以向左走，也可以向右走。如圖10一1所示。 問(wèn)題：當(dāng)三角形數(shù)塔給出之后，找出一條從第一層到達(dá)底層的路徑，使路徑的問(wèn)題：當(dāng)三角形數(shù)塔給出之后，找出一條從第一層到達(dá)底層的路徑，使路徑的值最大。若這樣的路徑存在多條，任意給出一條即可。值最大。若這樣的路徑存在多條，任意給出一條即可。 21二維數(shù)組二維數(shù)組 D(X,y)描述問(wèn)題，描述問(wèn)題，D(X,y)表示從頂層到達(dá)第表示從頂層到達(dá)第X層第層第y個(gè)位置的

16、最小路徑得分。個(gè)位置的最小路徑得分。階段分析：D(1,1)=13 到第x層的第y個(gè)位置有兩種可能，要么走右分支 得到，要么走左分支得到。l D(X,y)minD(X-1,y)，D(X-1,y-1+a(X,y)l D(1,1)a(1,1) 22拓展：棧（拓展：棧（vijos 1122） 【問(wèn)題背景】棧是計(jì)算機(jī)中經(jīng)典的數(shù)據(jù)結(jié)構(gòu)，簡(jiǎn)單的說(shuō)，棧就是限制在一端進(jìn)行插入刪除操作的線性表。棧有兩種最重要的操作，即pop（從棧頂彈出一個(gè)元素）和push（將一個(gè)元素進(jìn)棧）。寧寧考慮的是這樣一個(gè)問(wèn)題：一個(gè)操作數(shù)序列，從1，2，一直到n（圖示為1到3的情況），棧A的深度大于n?，F(xiàn)在可以進(jìn)行兩種操作，1.將一個(gè)數(shù)，從

17、操作數(shù)序列的頭端移到棧的頭端（對(duì)應(yīng)數(shù)據(jù)結(jié)構(gòu)棧的push操作）2. 將一個(gè)數(shù)，從棧的頭端移到輸出序列的尾端（對(duì)應(yīng)數(shù)據(jù)結(jié)構(gòu)棧的pop操作）23使用這兩種操作，由一個(gè)操作數(shù)序列就可以得到一系列的輸出使用這兩種操作，由一個(gè)操作數(shù)序列就可以得到一系列的輸出序列，下圖所示為由序列，下圖所示為由1 2 3生成序列生成序列2 3 1的過(guò)程。（原始狀態(tài)如的過(guò)程。（原始狀態(tài)如上圖所示）上圖所示）12312313222323124你的程序?qū)?duì)給定的你的程序?qū)?duì)給定的n，計(jì)算并輸出由操作數(shù)序列，計(jì)算并輸出由操作數(shù)序列1，2，n經(jīng)過(guò)操經(jīng)過(guò)操作可能得到的輸出序列的總數(shù)。作可能得到的輸出序列的總數(shù)?！据斎敫袷捷斎敫袷健枯斎?/p>

18、文件只含一個(gè)整數(shù)輸入文件只含一個(gè)整數(shù)n（1n18）【輸出格式輸出格式】輸出文件只有一行，即可能輸出序列的總數(shù)目輸出文件只有一行，即可能輸出序列的總數(shù)目【輸入樣例輸入樣例】3【輸出樣例輸出樣例】525例題七：最長(zhǎng)公共子序列例題七：最長(zhǎng)公共子序列l(wèi)一個(gè)給定序列的子序列是在該序列中刪去若干元素后得到的序列。l給定兩個(gè)序列X和Y，當(dāng)另一序列Z既是X的子序列又是Y的子序列時(shí)，稱Z是序列X和Y的公共子序列。l最長(zhǎng)公共子序列:公共子序列中長(zhǎng)度最長(zhǎng)的子序列。l最長(zhǎng)公共子序列問(wèn)題 給定兩個(gè)序列X=x1,x2,xm和Y=y1,y2, yn，找出X和Y的一個(gè)最長(zhǎng)公共子序列。l例如: X = (A, B, C, B,

19、 D, A, B) X的子序列:l所有X的子集(集合中元素按原來(lái)在X中的順序排列) (A, B, D), (B, C, D, B), 等等.26例子例子X(jué) = (A, B, C, B, D, A, B) X = (A, B, C, B, D, A, B)Y = (B, D, C, A, B, A) Y = (B, D, C, A, B, A)l(B, C, B, A)和(B, D, A, B)都是X和Y 的最長(zhǎng)公共子序列(長(zhǎng)度為4) l但是,(B, C, A)就不是X和Y的最長(zhǎng)公共子序列27窮舉法窮舉法l對(duì)于每一個(gè)Xm的子序列,驗(yàn)證它是否是Yn的子序列.lXm有2m個(gè)子序列l(wèi)每個(gè)子序列需要o(

20、n)的時(shí)間來(lái)驗(yàn)證它是否是Yn的子序列.l從Yn的第一個(gè)字母開(kāi)始掃描下去,如果不是則從第二個(gè)開(kāi)始l運(yùn)行時(shí)間: o(n2m)28l給定一個(gè)序列Xm = (x1, x2, , xm),我們定義Xm的第i個(gè)前綴為:Xi = ( x1, x2, , xi ) i = 0, 1, 2, , mci, j為序列Xi = (x1, x2, , xi)和Yj = (y1, y2, , yj)的最長(zhǎng)公共子序列的長(zhǎng)度.： 設(shè)序列Xm=x1,x2,xm和Yn=y1,y2,yn的一個(gè)最長(zhǎng)公共子序列為Zk=z1,z2,zk，則1.若xm=yn，則zk=xm=yn，且Zk-1是Xm-1和Yn-1的最長(zhǎng)公共子序列。2.若xm

21、yn，且zkxm，則Zk是Xm-1和Yn的最長(zhǎng)公共子序列。3.若xmyn，且zk yn ，則Zk是Xm和Yn-1的最長(zhǎng)公共子序列。步驟步驟1步驟步驟229狀態(tài)轉(zhuǎn)移方程狀態(tài)轉(zhuǎn)移方程0if 0 o r 0 , 1 , 1 1if , 0 a n d ,m a x ( 1 , , 1 )if , 0 a n d .ijijijcij ci jijx yci jcijijx y= = - -+=- 00000000000yj:xmy1y2ynx1x2xii012nm120firstsecond步驟步驟330附加信息附加信息00000000000yj:DACFABxiji012nm120矩陣 bi, j

22、:l它告訴我們要獲得最優(yōu)結(jié)果應(yīng)該如何選擇l如果 xi = yjbi, j = 1l如果 ci - 1, j ci, j-1bi, j = 2否則bi, j = 333CDci,j-1ci-1,j0if 0 o r 0 , 1 , 1 1if , 0 a n d ,m a x ( 1 , , 1 )if , 0 a n d .ijijijcij ci jijx yci jcijijx y= = - -+=- 31LCS-LENGTH(X, Y, m, n)1 for i 1 to m do ci, 0 02 for j 0 to n do c0, j 03 for i 1 to m do4 fo

23、r j 1 to n do5 if xi = yj6 then ci, j ci - 1, j - 1 + 17 bi, j “ ”8 else if ci - 1, j ci, j - 19 then ci, j ci - 1, j10 bi, j “”11 else ci, j ci, j - 112 bi, j “”13 return c and b運(yùn)行時(shí)間: (nm)32例子例子X(jué) = (B, D, C, A, B, A)Y = (A, B, C, B, D, A,B)0126345yjBDACAB51203467DABxiCBAB00000000000000000 11 1 1111

24、 2211 2222 1122 331 222331232 3 4 1223 44如果 xi = yj bi, j = “ ”如果 ci - 1, jci, j-1bi, j = “ ”否則bi, j = “ ”33找出最長(zhǎng)共同子序列找出最長(zhǎng)共同子序列PRINT-LCS(b, X, i, j)1 if i = 0 or j = 02 then return3 if bi, j = 4 then PRINT-LCS(b, X, i - 1, j - 1)5 print xi6 elseif bi, j = 7 then PRINT-LCS(b, X, i - 1, j)8 else PRINT-

25、LCS(b, X, i, j - 1)34例題例題8：0-1背包問(wèn)題背包問(wèn)題l小偷有一個(gè)可承受W的背包l有n件物品: 第i個(gè)物品價(jià)值vi 且重wil目標(biāo): l找到xi使得對(duì)于所有的xi = 0, 1, i = 1, 2, ., n wixi W 并且 xivi 最大部分背包問(wèn)題35最優(yōu)子結(jié)構(gòu)最優(yōu)子結(jié)構(gòu)l考慮最多重W的物品且價(jià)值最高l如果我們把j物品從背包中拿出來(lái) 剩下的裝載一定是取自n-1個(gè)物品使得不超過(guò)載重量W wj并且所裝物品價(jià)值最高的裝載360-1背包問(wèn)題的動(dòng)態(tài)規(guī)劃背包問(wèn)題的動(dòng)態(tài)規(guī)劃 對(duì)于每一個(gè)物品對(duì)于每一個(gè)物品i，都有兩種情況需要考慮，都有兩種情況需要考慮 第第1種情況種情況:物品物品

26、i的重量的重量wiw,即小偷不拿物品即小偷不拿物品i P(i, w) = P(i - 1, w)P(i, w) 考慮考慮前前i件物品所件物品所能獲得的最高價(jià)值能獲得的最高價(jià)值,其中其中w是是背包的承受力背包的承受力P（i，w）P(i-1,w) 當(dāng)wi w then6 Pi,w Pi-1, w;7 else8 Pi,w maxPi-1, w, Pi-1,w-wi + vi運(yùn)行時(shí)間: (nW)380-1背包問(wèn)題的動(dòng)態(tài)規(guī)劃背包問(wèn)題的動(dòng)態(tài)規(guī)劃000000000000000000:n1w - wiWi-10firstP(i, w) = max vi + P(i - 1, w-wi), P(i - 1,

27、w) 帶走物品i不帶走物品iiwsecond39P(i, w) = max vi + P(i - 1, w-wi), P(i - 1, w) 0000000000物品重量?jī)r(jià)值12122110332042150123451234W = 5012121212101222222210122230321015253037P(1, 1) = P(1, 2) = P(1, 3) = P(1, 4) = P(1, 5) = P(2, 1)= P(2, 2)= P(2, 3)= P(2, 4)= P(2, 5)= P(3, 1)= P(3, 2)= P(3, 3)= P(3, 4)= P(4, 5)= P(4

28、, 1)= P(4, 2)= P(4, 3)= P(4, 4)= P(4, 5)= max12+0, 0 = 12max12+0, 0 = 12max12+0, 0 = 12max12+0, 0 = 12max10+0, 0 = 10max10+0, 12 = 12max10+12, 12 = 22max10+12, 12 = 22max10+12, 12 = 22P(2,1) = 10P(2,2) = 12max20+0, 22=22max20+10,22=30max20+12,22=32P(3,1) = 10max15+0, 12 = 15max15+10, 22=25max15+12,

29、30=30max15+22, 32=370P(0, 1) = 0wi40構(gòu)造最優(yōu)解法構(gòu)造最優(yōu)解法000000000001234512340121212121012222222101222303210152530370l從 P(n, W)開(kāi)始l當(dāng)往左上走物品i被帶走l當(dāng)直往上走物品i未被帶走物品4物品2物品141子問(wèn)題的重復(fù)子問(wèn)題的重復(fù)000000000000000000:n1Wi-10P(i, w) = max vi + P(i - 1, w-wi), P(i - 1, w) iw例如: 所有用灰色表示的子問(wèn)題都取決于P(i-1, w)子問(wèn)題的重復(fù)子問(wèn)題的重復(fù)10010110810868100

30、6282861001623823816510000000000000111111111例子: n=5, p=6,3,5,4,6, w=2,2,6,5,4, W=1043拓展拓展1：裝箱問(wèn)題：裝箱問(wèn)題 （vijos 1133）有一個(gè)箱子容量為v(正整數(shù)，ov20000)，同時(shí)有n個(gè)物品(on30)，每個(gè)物品有一個(gè)體積 (正整數(shù))。要求從 n 個(gè)物品中，任取若千個(gè)裝入箱內(nèi)，使箱子的剩余空間為最小。 輸入格式輸入格式 Input Format 第一行，一個(gè)整數(shù)，表示箱子容量；第二行，一個(gè)整數(shù)，表示有n個(gè)物品；接下來(lái)n行，分別表示這n個(gè)物品的各自體積。 輸出格式輸出格式 Output Format 一

31、個(gè)整數(shù)，表示箱子剩余空間。 樣例輸入樣例輸入 Sample Input 2468312797樣例輸出樣例輸出 Sample Output 044拓展拓展2：采藥：采藥 (vijos1104) 辰辰是個(gè)天資聰穎的孩子，他的夢(mèng)想是成為世界上最偉大的醫(yī)師。為辰辰是個(gè)天資聰穎的孩子，他的夢(mèng)想是成為世界上最偉大的醫(yī)師。為此，他想拜附近最有威望的醫(yī)師為師。醫(yī)師為了判斷他的資質(zhì)，給他出了此，他想拜附近最有威望的醫(yī)師為師。醫(yī)師為了判斷他的資質(zhì)，給他出了一個(gè)難題。醫(yī)師把他帶到一個(gè)到處都是草藥的山洞里對(duì)他說(shuō)：一個(gè)難題。醫(yī)師把他帶到一個(gè)到處都是草藥的山洞里對(duì)他說(shuō)：“孩子，這孩子，這個(gè)山洞里有一些不同的草藥，采每一株

32、都需要一些時(shí)間，每一株也有它自個(gè)山洞里有一些不同的草藥，采每一株都需要一些時(shí)間，每一株也有它自身的價(jià)值。我會(huì)給你一段時(shí)間，在這段時(shí)間里，你可以采到一些草藥。如身的價(jià)值。我會(huì)給你一段時(shí)間，在這段時(shí)間里，你可以采到一些草藥。如果你是一個(gè)聰明的孩子，你應(yīng)該可以讓采到的草藥的總價(jià)值最大。果你是一個(gè)聰明的孩子，你應(yīng)該可以讓采到的草藥的總價(jià)值最大。” 如果你是辰辰，你能完成這個(gè)任務(wù)嗎？如果你是辰辰，你能完成這個(gè)任務(wù)嗎？輸入格式輸入格式 Input Format 輸入的第一行有兩個(gè)整數(shù)T（1 = T = 1000）和M（1 = M = 100），用一個(gè)空格隔開(kāi)，T代表總共能夠用來(lái)采藥的時(shí)間，M代表山洞里的草

33、藥的數(shù)目。接下來(lái)的M行每行包括兩個(gè)在1到100之間（包括1和100）的整數(shù)，分別表示采摘某株草藥的時(shí)間和這株草藥的價(jià)值。 輸出格式輸出格式 Output Format 輸出包括一行，這一行只包含一個(gè)整數(shù)，表示在規(guī)定的時(shí)間內(nèi)，可以采到的草藥的最大總價(jià)值。 樣例輸入樣例輸入 Sample Input 70 371 10069 11 2樣例輸出樣例輸出 Sample Output 345拓展拓展3：開(kāi)心的金明：開(kāi)心的金明 （vijos 1317） 金明今天很開(kāi)心，家里購(gòu)置的新房就要領(lǐng)鑰匙了，新房里有一間他自己專用的很寬敞的房間。更讓他高興的是，媽媽昨天對(duì)他說(shuō)：“你的房間需要購(gòu)買哪些物品，怎么布置，你

34、說(shuō)了算，只要不超過(guò)N 元錢就行”。今天一早金明就開(kāi)始做預(yù)算，但是他想買的東西太多了，肯定會(huì)超過(guò)媽媽限定的N 元。于是，他把每件物品規(guī)定了一個(gè)重要度，分為5 等：用整數(shù)15 表示，第5 等最重要。他還從因特網(wǎng)上查到了每件物品的價(jià)格（都是整數(shù)元）。他希望在不超過(guò)N 元（可以等于N 元）的前提下，使每件物品的價(jià)格與重要度的乘積的總和最大。設(shè)第j 件物品的價(jià)格為vj，重要度為wj，共選中了k 件物品，編號(hào)依次為j1.jk，則所求的總和為：vj1*wj1+.+vjk*wjk請(qǐng)你幫助金明設(shè)計(jì)一個(gè)滿足要求的購(gòu)物單. 輸入格式輸入格式 Input Format 輸入的第1 行，為兩個(gè)正整數(shù)，用一個(gè)空格隔開(kāi)：N

35、 m（其中N（30000）表示總錢數(shù)，m(25)為希望購(gòu)買物品的個(gè)數(shù)。）從第2 行到第m+1 行，第j 行給出了編號(hào)為j-1的物品的基本數(shù)據(jù)，每行有2 個(gè)非負(fù)整數(shù)v p（其中v 表示該物品的價(jià)格（v10000），p 表示該物品的重要度（15） 46輸出格式輸出格式 Output Format 輸出只有一個(gè)正整數(shù)，為不超過(guò)總錢數(shù)的物品的價(jià)格與重要度乘積的總和的最大值（100000000） 樣例輸入樣例輸入 Sample Input 1000 5800 2400 5300 5400 3200 2樣例輸出樣例輸出 Sample Output 390047拓展拓展4：金明的預(yù)算方案：金明的預(yù)算方案 (

36、vijos 1313 )金明今天很開(kāi)心，家里購(gòu)置的新房就要領(lǐng)鑰匙了，新房里有一間金明自己專用的很寬敞的房間。更讓他高興的是，媽媽昨天對(duì)他說(shuō)：“你的房間需要購(gòu)買哪些物品，怎么布置，你說(shuō)了算，只要不超過(guò)N元錢就行”。今天一早，金明就開(kāi)始做預(yù)算了，他把想買的物品分為兩類：主件與附件，附件是從屬于某個(gè)主件的，下表就是一些主件與附件的例子：主件 附件電腦 打印機(jī)，掃描儀書柜 圖書書桌 臺(tái)燈，文具工作椅 無(wú)如果要買歸類為附件的物品，必須先買該附件所屬的主件。每個(gè)主件可以有0個(gè)、1個(gè)或2個(gè)附件。附件不再有從屬于自己的附件。金明想買的東西很多，肯定會(huì)超過(guò)媽媽限定的N元。于是，他把每件物品規(guī)定了一個(gè)重要度，分為

37、5等：用整數(shù)15表示，第5等最重要。他還從因特網(wǎng)上查到了每件物品的價(jià)格（都是10元的整數(shù)倍）。他希望在不超過(guò)N元（可以等于N元）的前提下，使每件物品的價(jià)格與重要度的乘積的總和最大。設(shè)第j件物品的價(jià)格為vj，重要度為wj，共選中了k件物品，編號(hào)依次為j1，j2，jk，則所求的總和為：vj1*wj1+vj2*wj2+ +vjk*wjk。（其中*為乘號(hào)）請(qǐng)你幫助金明設(shè)計(jì)一個(gè)滿足要求的購(gòu)物單。48輸入格式輸入格式 Input Format 輸入文件的第1行，為兩個(gè)正整數(shù)，用一個(gè)空格隔開(kāi)：N m 其中N（32000）表示總錢數(shù)，m（60）為希望購(gòu)買物品的個(gè)數(shù)。）從第2行到第m+1行，第j行給出了編號(hào)為j

38、-1的物品的基本數(shù)據(jù)，每行有3個(gè)非負(fù)整數(shù)v p q（其中v表示該物品的價(jià)格（v0，表示該物品為附件，q是所屬主件的編號(hào)）輸出格式輸出格式 Output Format 輸出文件只有一個(gè)正整數(shù)，為不超過(guò)總錢數(shù)的物品的價(jià)格與重要度乘積的總和的最大值（200000）。 樣例輸入樣例輸入 Sample Input 1000 5800 2 0400 5 1300 5 1400 3 0500 2 0樣例輸出樣例輸出 Sample Output 220049例題例題9：石子歸并：石子歸并描述：在一個(gè)圓形操場(chǎng)的四周擺放著描述：在一個(gè)圓形操場(chǎng)的四周擺放著N堆石子堆石子(N= 100),現(xiàn)要將石子有次序現(xiàn)要將石子有

39、次序地合并成一堆地合并成一堆.規(guī)定每次只能選取相鄰的兩堆合并成新的一堆規(guī)定每次只能選取相鄰的兩堆合并成新的一堆,并將新的一堆并將新的一堆的石子數(shù)的石子數(shù),記為該次合并的得分記為該次合并的得分.編一程序編一程序,由文件讀入堆棧數(shù)由文件讀入堆棧數(shù)N及每堆棧的石及每堆棧的石子數(shù)子數(shù)(=20).(!)選擇一種合并石子的方案選擇一種合并石子的方案,使用權(quán)得做使用權(quán)得做N1次合并次合并,得分的總和最小得分的總和最小;(2)選擇一種合并石子的方案選擇一種合并石子的方案,使用權(quán)得做使用權(quán)得做N1次合并次合并,得分的總和最小得分的總和最小;輸入數(shù)據(jù)輸入數(shù)據(jù):第一行為石子堆數(shù)第一行為石子堆數(shù)N;第二行為每堆的石子

40、數(shù)第二行為每堆的石子數(shù),每?jī)蓚€(gè)數(shù)之間用一個(gè)空格每?jī)蓚€(gè)數(shù)之間用一個(gè)空格分隔分隔.輸出數(shù)據(jù)輸出數(shù)據(jù):從第一至第從第一至第N行為得分最小的合并方案行為得分最小的合并方案.第第N+1行行是空行是空行.從第從第N+2行到第行到第2N+1行是得分最大合并方行是得分最大合并方案案.每種合并方案用每種合并方案用N行表示行表示,其中第其中第i行行(1=i=N)表示第表示第i次合并前各堆的石子數(shù)次合并前各堆的石子數(shù)(依順時(shí)針次序輸出依順時(shí)針次序輸出,哪一堆先輸出均可哪一堆先輸出均可).要求將待合并的兩堆石子數(shù)以要求將待合并的兩堆石子數(shù)以相應(yīng)的負(fù)數(shù)表示相應(yīng)的負(fù)數(shù)表示.輸入輸出范例輸入輸出范例:輸入輸入:44 5 9

41、 4 輸出輸出:最小最小43最大最大5450輸入輸入:44 5 9 4 輸出輸出: 拓：輸出合并的方案：拓：輸出合并的方案：51用用i，j表示一個(gè)從第表示一個(gè)從第i堆數(shù)起，順時(shí)針數(shù)堆數(shù)起，順時(shí)針數(shù)j堆時(shí)的子序列堆時(shí)的子序列第第i堆、第堆、第i堆、堆、第（、第（ij1）mod n堆堆 fi，j將子序列將子序列i，j中的中的j堆石子合并成一堆堆石子合并成一堆的最佳得分和；（結(jié)果數(shù)組）的最佳得分和；（結(jié)果數(shù)組）ci，j將將i，j一分為二，其中子序列的堆一分為二，其中子序列的堆數(shù)；（記錄分隔點(diǎn)）數(shù)；（記錄分隔點(diǎn)）打印合并方案時(shí)使用打印合并方案時(shí)使用52顯然，對(duì)每一堆石子來(lái)說(shuō)，它的fi， ci， （iN

42、）對(duì)于子序列i，j來(lái)說(shuō)，若求最小得分總和，fi，j的初始值為； 若求最大得分總和，fi，j的初始值為。（iN，jN）。規(guī)劃的方向是順推。先考慮含二堆石子的N個(gè)子序列（各子序列分別從第堆、第堆、第N堆數(shù)起，順時(shí)針數(shù)堆）的合并方案f，f，fN，c，c，cN，然后考慮含三堆石子的個(gè)子序列（各子序列分別從第堆、第堆、第堆數(shù)起，順時(shí)針數(shù)堆）的合并方案f，f，fN，c，c，cN，依次類推，直至考慮了含N堆石子的N個(gè)子序列（各子序列分別從第堆、第堆、 、第N堆數(shù)起，順時(shí)針數(shù)N堆）的合并方案f，N，f，N，fN，Nc，N，c，N，cN，N最后，在子序列，N，N，N，N中，選擇得分總和（f值）最?。ɑ蜃畲螅┑囊?/p>

43、個(gè)子序列i，N（iN），由此出發(fā)倒推合并過(guò)程。 53例如對(duì)（圖624）中的堆石子，按動(dòng)態(tài)規(guī)劃方程順推最小得分和。 依次得出含二堆石子的個(gè)子序列的合并方案f， f， f ， c， c， c，f， f， f，c， c， c，含三堆石子的個(gè)子序列的合并方案f， f， f， c， c， c，f， f， f，c， c， c，含四堆石子的個(gè)子序列的合并方案f， f， f，c， c， c，f， f， f，c， c， c，例題：例題： 54F(I,j)= f (i,1)=0 j=1, 1=i=nmaxfi，kfx，j-kt , 1=k=j-1其中，x（ik1） mod n +1 即第i堆起，順時(shí)針數(shù)k1堆的堆序號(hào)。 tai+ai+1+.+aj, 即將分開(kāi)的兩堆合并為一堆的得分。