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

動(dòng)態(tài)規(guī)劃例題眾多詳細(xì)講解第一頁(yè)，共五十九頁(yè)，編輯于2023年，星期日F(n)=

1 ifn=0or1F(n-1)+F(n-2) ifn>1n012345678910F(n)1123581321345589斐波納契數(shù)列F(n)2第二頁(yè)，共五十九頁(yè)，編輯于2023年，星期日遞歸

vs動(dòng)態(tài)規(guī)劃遞歸版本:F(n)1 if

n=0orn=1then2 return13 else4 returnF(n-1)+F(n-2)動(dòng)態(tài)規(guī)劃:F(n)1 A[0]

=

A[1]←

12 for

i

←2to

n

do3 A[i]

←

A[i-1]

+

A[i-2]4 returnA[n]太慢!有效率!算法復(fù)雜度是

O(n)3第三頁(yè)，共五十九頁(yè)，編輯于2023年，星期日方法概要構(gòu)造一個(gè)公式，它表示一個(gè)問題的解是與它的子問題的解相關(guān)的公式.

E.g.F(n)=F(n-1)+F(n-2).為這些子問題做索引

，以便它們能夠在表中更好的存儲(chǔ)與檢索

(i.e.,數(shù)組array【】)以自底向上的方法來填寫這表格;首先填寫最小子問題的解.這就保證了當(dāng)我們解決一個(gè)特殊的子問題時(shí),可以利用比它更小的所有可利用的子問題的解.由于歷史原因,我們稱這種方法為：動(dòng)態(tài)規(guī)劃.在上世紀(jì)40年代末

(計(jì)算機(jī)普及很少時(shí)),

這些規(guī)劃設(shè)計(jì)是與”列表“方法相關(guān)的.4第四頁(yè)，共五十九頁(yè)，編輯于2023年，星期日動(dòng)態(tài)規(guī)劃算法算法思想將待求解的問題分解成若干個(gè)子問題，并存儲(chǔ)子問題的解而避免計(jì)算重復(fù)的子問題，并由子問題的解得到原問題的解。動(dòng)態(tài)規(guī)劃算法通常用于求解具有某種最優(yōu)性質(zhì)的問題。動(dòng)態(tài)規(guī)劃算法的基本要素：最優(yōu)子結(jié)構(gòu)性質(zhì)和重疊子問題。原理5第五頁(yè)，共五十九頁(yè)，編輯于2023年，星期日最優(yōu)子結(jié)構(gòu)性質(zhì)：?jiǎn)栴}的最優(yōu)解包含著它的子問題的最優(yōu)解。即不管前面的策略如何，此后的決策必須是基于當(dāng)前狀態(tài)（由上一次決策產(chǎn)生）的最優(yōu)決策。重疊子問題：在用遞歸算法自頂向下解問題時(shí)，每次產(chǎn)生的子問題并不總是新問題，有些問題被反復(fù)計(jì)算多次。對(duì)每個(gè)子問題只解一次，然后將其解保存起來，以后再遇到同樣的問題時(shí)就可以直接引用，不必重新求解。原理6第六頁(yè)，共五十九頁(yè)，編輯于2023年，星期日動(dòng)態(tài)規(guī)劃解決問題的基本特征1.動(dòng)態(tài)規(guī)劃一般解決最值（最優(yōu)，最大，最小，最長(zhǎng)……）問題；2.動(dòng)態(tài)規(guī)劃解決的問題一般是離散的，可以分解（劃分階段）的；3.動(dòng)態(tài)規(guī)劃解決的問題必須包含最優(yōu)子結(jié)構(gòu)，即可以由（n－1）的最優(yōu)推導(dǎo)出n的最優(yōu)原理7第七頁(yè)，共五十九頁(yè)，編輯于2023年，星期日動(dòng)態(tài)規(guī)劃算法的4個(gè)步驟：

1.刻畫最優(yōu)解的結(jié)構(gòu)特性.（一維，二維，三維數(shù)組）

2.遞歸的定義最優(yōu)解.（狀態(tài)轉(zhuǎn)移方程）

3.以自底向上的方法來計(jì)算最優(yōu)解.4.從計(jì)算得到的解來構(gòu)造一個(gè)最優(yōu)解.解決問題的基本步驟原理8第八頁(yè)，共五十九頁(yè)，編輯于2023年，星期日實(shí)例例題一.斐波納契數(shù)列F(n)F(n)=

1 ifn=0or1F(n-1)+F(n-2) ifn>1步驟1：用F（n）表示在斐波納契數(shù)列中第n個(gè)數(shù)的值；步驟2：狀態(tài)轉(zhuǎn)移方程：步驟3：以自底向上的方法來計(jì)算最優(yōu)解n012345678910F(n)1123581321345589步驟4：在數(shù)組中分析構(gòu)造出問題的解；9第九頁(yè)，共五十九頁(yè)，編輯于2023年，星期日例題二.輸入n，求出n！F(n)=

1 ifn=0or1F(n-1)*n ifn>1步驟1：用F（n）表示n！的值；步驟2：狀態(tài)轉(zhuǎn)移方程：步驟3：以自底向上的方法來計(jì)算最優(yōu)解n012345678910F(n)112624120720實(shí)例10第十頁(yè)，共五十九頁(yè)，編輯于2023年，星期日例題三：排隊(duì)買票問題

一場(chǎng)演唱會(huì)即將舉行?，F(xiàn)有n個(gè)歌迷排隊(duì)買票，一個(gè)人買一張，而售票處規(guī)定，一個(gè)人每次最多只能買兩張票。假設(shè)第i位歌迷買一張票需要時(shí)間Ti（1≤i≤n），隊(duì)伍中相鄰的兩位歌迷（第j個(gè)人和第j+1個(gè)人）也可以由其中一個(gè)人買兩張票，而另一位就可以不用排隊(duì)了，則這兩位歌迷買兩張票的時(shí)間變?yōu)镽j，假如Rj<Tj+Tj+1，這樣做就可以縮短后面歌迷等待的時(shí)間，加快整個(gè)售票的進(jìn)程?，F(xiàn)給出n,Tj和Rj，求使每個(gè)人都買到票的最短時(shí)間和方法。實(shí)例11第十一頁(yè)，共五十九頁(yè)，編輯于2023年，星期日分析：如果前i個(gè)人買票的最優(yōu)買票方式一確定，比如第i-1個(gè)人買一張票，則前i-1個(gè)人的買票方式也一定是最優(yōu)的。即問題的最優(yōu)解包含子問題的最優(yōu)解。12345i…in-1nn-2…步驟1：用F（i）表示前i個(gè)人買票的最優(yōu)方式，即所需最短時(shí)間；現(xiàn)在要決定F(i)需要考慮兩種情況：（1）第i個(gè)人的票自己買（2）第i個(gè)人的票由第i-1個(gè)人買步驟2：狀態(tài)轉(zhuǎn)移方程：min步驟3：以自底向上的方法來計(jì)算最優(yōu)解12第十二頁(yè)，共五十九頁(yè)，編輯于2023年，星期日程序的實(shí)現(xiàn)BuyTicks(T,R)1n←length[T]2f[0]←03f[1]←T[1]4fori←2ton

do5

f[i]←f[i-2]+R[i-1]6iff[i]

>f[i-1]+T[i]then7f[i]←f[i-1]+T[i]8returnf13第十三頁(yè)，共五十九頁(yè)，編輯于2023年，星期日實(shí)例例題四：求最長(zhǎng)不降子序列1．問題描述設(shè)有一個(gè)正整數(shù)的序列：b1,b2,…，bn，對(duì)于下標(biāo)i1<i2<…＜im，若有bi1≤bi2≤…≤bim則稱存在一個(gè)長(zhǎng)度為m的不下降序列。例如，下列數(shù)列

13791638243718441921226315

對(duì)于下標(biāo)i1=1，i2=4，i3=5，i4=9，i5=13，滿足13＜16＜38＜44＜63,則存在長(zhǎng)度為5的不下降序列。但是，我們看到還存在其他的不下降序列:i1=2，i2=3，i3=4，i4=8，i5＝10，i6=11，i7=12，i8=13，滿足：7＜9＜16＜18＜19＜21＜22＜63，則存在長(zhǎng)度為8的不下降序列。問題為：當(dāng)b1,b2,…，bn給出之后，求出最長(zhǎng)的不下降序列。步驟1：用F（i）表示第i項(xiàng)到最后一項(xiàng)最長(zhǎng)不下降序列的長(zhǎng)度的值；步驟2：狀態(tài)轉(zhuǎn)移方程；d[i]表示數(shù)列中第i項(xiàng)的值；步驟3：以自底向上的方法來計(jì)算最優(yōu)解14第十四頁(yè)，共五十九頁(yè)，編輯于2023年，星期日拓展1：

攔截導(dǎo)彈

（vijos1303）某國(guó)為了防御敵國(guó)的導(dǎo)彈襲擊，發(fā)展出一種導(dǎo)彈攔截系統(tǒng)。但是這種導(dǎo)彈攔截系統(tǒng)有一個(gè)缺陷：雖然它的第一發(fā)炮彈能夠到達(dá)任意的高度，但是以后每一發(fā)炮彈都不能高于前一發(fā)的高度。某天，雷達(dá)捕捉到敵國(guó)的導(dǎo)彈來襲。由于該系統(tǒng)還在試用階段，所以只有一套系統(tǒng)，因此有可能不能攔截所有的導(dǎo)彈。輸入導(dǎo)彈依次飛來的高度（雷達(dá)給出的高度數(shù)據(jù)是不大于30000的正整數(shù)），計(jì)算這套系統(tǒng)最多能攔截多少導(dǎo)彈，如果要攔截所有導(dǎo)彈最少要配備多少套這種導(dǎo)彈攔截系統(tǒng)。

樣例：

INPUTOUTPUT389207155300299170158656（最多能攔截的導(dǎo)彈數(shù)）

2（要攔截所有導(dǎo)彈最少要配備的系統(tǒng)數(shù)）15第十五頁(yè)，共五十九頁(yè)，編輯于2023年，星期日拓展2：低價(jià)購(gòu)買

“低價(jià)購(gòu)買”這條建議是在奶牛股票市場(chǎng)取得成功的一半規(guī)則。要想被認(rè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à)格清單：日期123456789101112價(jià)格686954646864706778629887最優(yōu)秀的投資者可以購(gòu)買最多4次股票，可行方案中的一種是：日期25610價(jià)格69686462輸入第1行:N(1<=N<=5000)，股票發(fā)行天數(shù)第2行:N個(gè)數(shù)，是每天的股票價(jià)格。輸出輸出文件僅一行包含兩個(gè)數(shù):最大購(gòu)買次數(shù)和擁有最大購(gòu)買次數(shù)的方案數(shù)(<=231)當(dāng)二種方案“看起來一樣”時(shí)（就是說它們構(gòu)成的價(jià)格隊(duì)列一樣的時(shí)候）,這2種方案被認(rèn)為是相同的。16第十六頁(yè)，共五十九頁(yè)，編輯于2023年，星期日拓展3：合唱隊(duì)形（vijis1098）N位同學(xué)站成一排，音樂老師要請(qǐng)其中的(N-K)位同學(xué)出列，使得剩下的K位同學(xué)排成合唱隊(duì)形。

合唱隊(duì)形是指這樣的一種隊(duì)形：設(shè)K位同學(xué)從左到右依次編號(hào)為1，2…，K，他們的身高分別為T1，T2，…，TK，

則他們的身高滿足T1<...<Ti>Ti+1>…>TK(1<=i<=K)。

你的任務(wù)是，已知所有N位同學(xué)的身高，計(jì)算最少需要幾位同學(xué)出列，可以使得剩下的同學(xué)排成合唱隊(duì)形。輸入的第一行是一個(gè)整數(shù)N(2<=N<=100)，表示同學(xué)的總數(shù)。第一行有n個(gè)整數(shù)，用空格分隔，第i個(gè)整數(shù)Ti(130<=Ti<=230)是第i位同學(xué)的身高(厘米)。輸出包括一行，這一行只包含一個(gè)整數(shù)，就是最少需要幾位同學(xué)出列。樣例輸入8186186150200160130197220樣例輸出：417第十七頁(yè)，共五十九頁(yè)，編輯于2023年，星期日例題五.馬攔過河卒實(shí)例[問題描述]:

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

輸入：

6632

輸出：

17

18第十八頁(yè)，共五十九頁(yè)，編輯于2023年，星期日步驟1：用F（X,Y）表示到棋盤上每個(gè)階段(X,Y)的路徑條數(shù)；步驟2：狀態(tài)轉(zhuǎn)移方程：步驟3：以自底向上的方法來計(jì)算最優(yōu)解分析：階段：棋盤上的每個(gè)可走的點(diǎn)；每個(gè)階段的求解；F（X,Y）=F(X-1,Y)+F(X,Y-1)其中，F(xiàn)（0,0)=1F(0,Y)=1F(X,0)=119第十九頁(yè)，共五十九頁(yè)，編輯于2023年，星期日例題六：數(shù)字三角形問題1．問題描述設(shè)有一個(gè)三角形的數(shù)塔，頂點(diǎn)結(jié)點(diǎn)稱為根結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)有一個(gè)整數(shù)數(shù)值。從頂點(diǎn)出發(fā)，可以向左走，也可以向右走。如圖10一1所示。問題：當(dāng)三角形數(shù)塔給出之后，找出一條從第一層到達(dá)底層的路徑，使路徑的值最大。若這樣的路徑存在多條，任意給出一條即可。20第二十頁(yè)，共五十九頁(yè)，編輯于2023年，星期日步驟1二維數(shù)組D(X,y)描述問題，D(X,y)表示從頂層到達(dá)第X層第y個(gè)位置的最小路徑得分。步驟2：狀態(tài)轉(zhuǎn)移方程階段分析：D(1,1)=13

到第x層的第y個(gè)位置有兩種可能，要么走右分支得到，要么走左分支得到。

D(X,y)＝min{D(X-1,y)，D(X-1,y-1}+a(X,y)D(1,1)＝a(1,1)21第二十一頁(yè)，共五十九頁(yè)，編輯于2023年，星期日拓展：棧（vijos1122）【問題背景】棧是計(jì)算機(jī)中經(jīng)典的數(shù)據(jù)結(jié)構(gòu)，簡(jiǎn)單的說，棧就是限制在一端進(jìn)行插入刪除操作的線性表。棧有兩種最重要的操作，即pop（從棧頂彈出一個(gè)元素）和push（將一個(gè)元素進(jìn)棧）。寧寧考慮的是這樣一個(gè)問題：一個(gè)操作數(shù)序列，從1，2，一直到n（圖示為1到3的情況），棧A的深度大于n。現(xiàn)在可以進(jìn)行兩種操作，1.將一個(gè)數(shù)，從操作數(shù)序列的頭端移到棧的頭端（對(duì)應(yīng)數(shù)據(jù)結(jié)構(gòu)棧的push操作）2.將一個(gè)數(shù)，從棧的頭端移到輸出序列的尾端（對(duì)應(yīng)數(shù)據(jù)結(jié)構(gòu)棧的pop操作）22第二十二頁(yè)，共五十九頁(yè)，編輯于2023年，星期日使用這兩種操作，由一個(gè)操作數(shù)序列就可以得到一系列的輸出序列，下圖所示為由123生成序列231的過程。（原始狀態(tài)如上圖所示）12312313222323123第二十三頁(yè)，共五十九頁(yè)，編輯于2023年，星期日你的程序?qū)?duì)給定的n，計(jì)算并輸出由操作數(shù)序列1，2，…，n經(jīng)過操作可能得到的輸出序列的總數(shù)。【輸入格式】輸入文件只含一個(gè)整數(shù)n（1≤n≤18）【輸出格式】輸出文件只有一行，即可能輸出序列的總數(shù)目【輸入樣例】3【輸出樣例】524第二十四頁(yè)，共五十九頁(yè)，編輯于2023年，星期日例題七：最長(zhǎng)公共子序列一個(gè)給定序列的子序列是在該序列中刪去若干元素后得到的序列。給定兩個(gè)序列X和Y，當(dāng)另一序列Z既是X的子序列又是Y的子序列時(shí)，稱Z是序列X和Y的公共子序列。最長(zhǎng)公共子序列:公共子序列中長(zhǎng)度最長(zhǎng)的子序列。最長(zhǎng)公共子序列問題給定兩個(gè)序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的一個(gè)最長(zhǎng)公共子序列。例如:

X=(A,B,C,B,D,A,B)X的子序列:所有X的子集(集合中元素按原來在X中的順序排列) (A,B,D),(B,C,D,B),等等.25第二十五頁(yè)，共五十九頁(yè)，編輯于2023年，星期日例子X=(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)(B,C,B,A)和(B,D,A,B)都是X和Y

的最長(zhǎng)公共子序列(長(zhǎng)度為4)但是,(B,C,A)就不是X和Y的最長(zhǎng)公共子序列26第二十六頁(yè)，共五十九頁(yè)，編輯于2023年，星期日窮舉法對(duì)于每一個(gè)Xm的子序列,驗(yàn)證它是否是Yn的子序列.Xm有2m個(gè)子序列每個(gè)子序列需要o(n)的時(shí)間來驗(yàn)證它是否是Yn的子序列.從Yn的第一個(gè)字母開始掃描下去,如果不是則從第二個(gè)開始運(yùn)行時(shí)間:o(n2m)27第二十七頁(yè)，共五十九頁(yè)，編輯于2023年，星期日給定一個(gè)序列Xm=(x1,x2,…,xm),我們定義Xm的第i個(gè)前綴為:

Xi=(x1,x2,…,xi)i=0,1,2,…,mc[i,j]為序列Xi=(x1,x2,…,xi)和Yj

=(y1,y2,…,yj)的最長(zhǎng)公共子序列的長(zhǎng)度.分析:最優(yōu)子結(jié)構(gòu)性質(zhì)：設(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≠yn，且zk≠xm，則Zk是Xm-1和Yn的最長(zhǎng)公共子序列。3.若xm≠yn，且zk≠yn，則Zk是Xm和Yn-1的最長(zhǎng)公共子序列。步驟1步驟228第二十八頁(yè)，共五十九頁(yè)，編輯于2023年，星期日狀態(tài)轉(zhuǎn)移方程00000000000yj:xmy1y2ynx1x2xii012nm120firstsecond步驟329第二十九頁(yè)，共五十九頁(yè)，編輯于2023年，星期日附加信息00000000000yj:DACFABxiji012nm120矩陣b[i,j]:它告訴我們要獲得最優(yōu)結(jié)果應(yīng)該如何選擇如果xi=yj

b[i,j]=1如果 c[i-1,j]≥c[i,j-1]

b[i,j]=2否則

b[i,j]=333CDc[i,j-1]c[i-1,j]30第三十頁(yè)，共五十九頁(yè)，編輯于2023年，星期日LCS-LENGTH(X,Y,m,n)1

for

i←1to

m

do

c[i,0]←02

for

j←0to

n

do

c[0,j]←03

for

i←1to

m

do4

for

j←1to

n

do5

if

xi=yj6

then

c[i,j]←c[i-1,j-1]+17 b[i,j]←“↖”8

elseif

c[i-1,j]≥c[i,j-1]9

then

c[i,j]←c[i-1,j]10 b[i,j]←“↑”11

else

c[i,j]←c[i,j-1]12 b[i,j]←“←”13

return

candb運(yùn)行時(shí)間:(nm)31第三十一頁(yè)，共五十九頁(yè)，編輯于2023年，星期日例子X=(B,D,C,A,B,A)Y=(A,B,C,B,D,A,B)0126345yjBDACAB51203467DABxiCBAB00000000000000000

11

1

1111

2211

2222

1122

331

222331232

3

4

1223

44如果xi=yj

b[i,j]=“

”如果 c[i-1,j]≥c[i,j-1]

b[i,j]=“”否則

b[i,j]=“”32第三十二頁(yè)，共五十九頁(yè)，編輯于2023年，星期日找出最長(zhǎng)共同子序列PRINT-LCS(b,X,i,j)1

if

i=0orj=02thenreturn3if

b[i,j]="↖"4then

PRINT-LCS(b,X,i-1,j-1)5printxi6elseif

b[i,j]="↑"7then

PRINT-LCS(b,X,i-1,j)8else

PRINT-LCS(b,X,i,j-1)33第三十三頁(yè)，共五十九頁(yè)，編輯于2023年，星期日例題8：0-1背包問題小偷有一個(gè)可承受W的背包有n件物品:第i個(gè)物品價(jià)值vi

且重wi目標(biāo):找到xi使得對(duì)于所有的xi={0,1},i=1,2,..,n wixiW

并且

xivi

最大部分背包問題34第三十四頁(yè)，共五十九頁(yè)，編輯于2023年，星期日最優(yōu)子結(jié)構(gòu)考慮最多重W的物品且價(jià)值最高如果我們把j物品從背包中拿出來剩下的裝載一定是取自n-1個(gè)物品使得不超過載重量W–wj并且所裝物品價(jià)值最高的裝載35第三十五頁(yè)，共五十九頁(yè)，編輯于2023年，星期日0-1背包問題的動(dòng)態(tài)規(guī)劃對(duì)于每一個(gè)物品i，都有兩種情況需要考慮第1種情況:物品i的重量wi<=w，小偷對(duì)物品i可拿或者不拿

P[i,w]=max{P[i-1,w],P[i-1,w-wi]+vi}第2種情況:物品i的重量wi>w,即小偷不拿物品i

P(i,w)=P(i-1,w)步驟1P(i,w)–考慮前i件物品所能獲得的最高價(jià)值,其中w是背包的承受力步驟2階段分析：P（i，w）＝P(i-1,w)當(dāng)wi<w（不夠裝不裝）maxP(i-1,w)夠裝但不裝p(i-1,w-wi)+pi夠裝而且裝36第三十六頁(yè)，共五十九頁(yè)，編輯于2023年，星期日Knapsack(S,W)1for

w

←0to

w1-1do

P[1,w]←0;2for

w

←

w1

to

W

do

P[1,w]←

v1;3for

i

←2to

n

do4for

w

←0to

W

do5if

wi>w

then6P[i,w]←

P[i-1,w];7else8P[i,w]←max{P[i-1,w],P[i-1,w-wi]+vi}運(yùn)行時(shí)間:(nW)37第三十七頁(yè)，共五十九頁(yè)，編輯于2023年，星期日0-1背包問題的動(dòng)態(tài)規(guī)劃000000000000000000:n1w-wiWi-10first

P(i,w)=max{vi

+P(i-1,w-wi),P(i-1,w)}帶走物品i不帶走物品iiwsecond38第三十八頁(yè)，共五十九頁(yè)，編輯于2023年，星期日P(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,1)=P(4,2)=P(4,3)=P(4,4)=P(4,5)=max{12+0,0}=12max{12+0,0}=12max{12+0,0}=12max{12+0,0}=12max{10+0,0}=10max{10+0,12}=12max{10+12,12}=22max{10+12,12}=22max{10+12,12}=22P(2,1)=10P(2,2)=12max{20+0,22}=22max{20+10,22}=30max{20+12,22}=32P(3,1)=10max{15+0,12}=15max{15+10,22}=25max{15+12,30}=30max{15+22,32}=370P(0,1)=0wi39第三十九頁(yè)，共五十九頁(yè)，編輯于2023年，星期日構(gòu)造最優(yōu)解法000000000001234512340121212121012222222101222303210152530370從P(n,W)開始當(dāng)往左上走物品i被帶走當(dāng)直往上走物品i未被帶走物品4物品2物品140第四十頁(yè)，共五十九頁(yè)，編輯于2023年，星期日子問題的重復(fù)000000000000000000:n1Wi-10

P(i,w)=max{vi

+P(i-1,w-wi),P(i-1,w)}iw例如:所有用灰色表示的子問題都取決于P(i-1,w)41第四十一頁(yè)，共五十九頁(yè)，編輯于2023年，星期日子問題的重復(fù)100101108108681006282861001623823816510000000000000111111111例子:

n=5,p=[6,3,5,4,6],w=[2,2,6,5,4],W=10第四十二頁(yè)，共五十九頁(yè)，編輯于2023年，星期日拓展1：裝箱問題（vijos1133）有一個(gè)箱子容量為v(正整數(shù)，o≤v≤20000)，同時(shí)有n個(gè)物品(o≤n≤30)，每個(gè)物品有一個(gè)體積(正整數(shù))。要求從n個(gè)物品中，任取若千個(gè)裝入箱內(nèi)，使箱子的剩余空間為最小。輸入格式InputFormat第一行，一個(gè)整數(shù)，表示箱子容量；

第二行，一個(gè)整數(shù)，表示有n個(gè)物品；

接下來n行，分別表示這n個(gè)物品的各自體積。輸出格式OutputFormat一個(gè)整數(shù)，表示箱子剩余空間。樣例輸入SampleInput2468312797樣例輸出SampleOutput043第四十三頁(yè)，共五十九頁(yè)，編輯于2023年，星期日拓展2：采藥(vijos1104)辰辰是個(gè)天資聰穎的孩子，他的夢(mèng)想是成為世界上最偉大的醫(yī)師。為此，他想拜附近最有威望的醫(yī)師為師。醫(yī)師為了判斷他的資質(zhì)，給他出了一個(gè)難題。醫(yī)師把他帶到一個(gè)到處都是草藥的山洞里對(duì)他說：“孩子，這個(gè)山洞里有一些不同的草藥，采每一株都需要一些時(shí)間，每一株也有它自身的價(jià)值。我會(huì)給你一段時(shí)間，在這段時(shí)間里，你可以采到一些草藥。如果你是一個(gè)聰明的孩子，你應(yīng)該可以讓采到的草藥的總價(jià)值最大?！?/p>

如果你是辰辰，你能完成這個(gè)任務(wù)嗎？

輸入格式InputFormat輸入的第一行有兩個(gè)整數(shù)T（1<=T<=1000）和M（1<=M<=100），用一個(gè)空格隔開，T代表總共能夠用來采藥的時(shí)間，M代表山洞里的草藥的數(shù)目。接下來的M行每行包括兩個(gè)在1到100之間（包括1和100）的整數(shù)，分別表示采摘某株草藥的時(shí)間和這株草藥的價(jià)值。輸出格式OutputFormat輸出包括一行，這一行只包含一個(gè)整數(shù)，表示在規(guī)定的時(shí)間內(nèi)，可以采到的草藥的最大總價(jià)值。樣例輸入SampleInput7037110069112樣例輸出SampleOutput344第四十四頁(yè)，共五十九頁(yè)，編輯于2023年，星期日拓展3：開心的金明（vijos1317）金明今天很開心，家里購(gòu)置的新房就要領(lǐng)鑰匙了，新房里有一間他自己專用的很寬敞的房間。更讓他高興的是，媽媽昨天對(duì)他說：“你的房間需要購(gòu)買哪些物品，怎么布置，你說了算，只要不超過N元錢就行”。今天一早金明就開始做預(yù)算，但是他想買的東西太多了，肯定會(huì)超過媽媽限定的N元。于是，他把每件物品規(guī)定了一個(gè)重要度，分為5等：用整數(shù)1~5表示，第5等最重要。他還從因特網(wǎng)上查到了每件物品的價(jià)格（都是整數(shù)元）。他希望在不超過N元（可以等于N元）的前提下，使每件物品的價(jià)格與重要度的乘積的總和最大。設(shè)第j件物品的價(jià)格為v[j]，重要度為w[j]，共選中了k件物品，編號(hào)依次為j1...jk，則所求的總和為：v[j1]*w[j1]+..+v[jk]*w[jk]請(qǐng)你幫助金明設(shè)計(jì)一個(gè)滿足要求的購(gòu)物單.輸入格式InputFormat輸入的第1行，為兩個(gè)正整數(shù)，用一個(gè)空格隔開：

Nm

（其中N（<30000）表示總錢數(shù)，m(<25)為希望購(gòu)買物品的個(gè)數(shù)。）

從第2行到第m+1行，第j行給出了編號(hào)為j-1

的物品的基本數(shù)據(jù)，每行有2個(gè)非負(fù)整數(shù)

vp

（其中v表示該物品的價(jià)格（v≤10000），p表示該物品的重要度（1~5））45第四十五頁(yè)，共五十九頁(yè)，編輯于2023年，星期日輸出格式OutputFormat輸出只有一個(gè)正整數(shù)，為不超過總錢數(shù)的物品的價(jià)格與重要度乘積的總和的

最大值（<100000000）樣例輸入SampleInput1000580024005300540032002樣例輸出SampleOutput390046第四十六頁(yè)，共五十九頁(yè)，編輯于2023年，星期日拓展4：金明的預(yù)算方案(vijos1313)金明今天很開心，家里購(gòu)置的新房就要領(lǐng)鑰匙了，新房里有一間金明自己專用的很寬敞的房間。更讓他高興的是，媽媽昨天對(duì)他說：“你的房間需要購(gòu)買哪些物品，怎么布置，你說了算，只要不超過N元錢就行”。今天一早，金明就開始做預(yù)算了，他把想買的物品分為兩類：主件與附件，附件是從屬于某個(gè)主件的，下表就是一些主件與附件的例子：

主件附件

電腦打印機(jī)，掃描儀

書柜圖書

書桌臺(tái)燈，文具

工作椅無

如果要買歸類為附件的物品，必須先買該附件所屬的主件。每個(gè)主件可以有0個(gè)、1個(gè)或2個(gè)附件。附件不再有從屬于自己的附件。金明想買的東西很多，肯定會(huì)超過媽媽限定的N元。于是，他把每件物品規(guī)定了一個(gè)重要度，分為5等：用整數(shù)1~5表示，第5等最重要。他還從因特網(wǎng)上查到了每件物品的價(jià)格（都是10元的整數(shù)倍）。他希望在不超過N元（可以等于N元）的前提下，使每件物品的價(jià)格與重要度的乘積的總和最大。

設(shè)第j件物品的價(jià)格為v[j]，重要度為w[j]，共選中了k件物品，編號(hào)依次為j1，j2，……，jk，則所求的總和為：v[j1]*w[j1]+v[j2]*w[j2]+…+v[jk]*w[jk]。（其中*為乘號(hào)）請(qǐng)你幫助金明設(shè)計(jì)一個(gè)滿足要求的購(gòu)物單。

47第四十七頁(yè)，共五十九頁(yè)，編輯于2023年，星期日輸入格式InputFormat輸入文件的第1行，為兩個(gè)正整數(shù)，用一個(gè)空格隔開：

N

m

其中N（<32000）表示總錢數(shù)，m（<60）為希望購(gòu)買物品的個(gè)數(shù)。）

從第2行到第m+1行，第j行給出了編號(hào)為j-1的物品的基本數(shù)據(jù)，每行有3個(gè)非負(fù)整數(shù)

v

p

q

（其中v表示該物品的價(jià)格（v<10000），p表示該物品的重要度（1~5），q表示該物品是主件還是附件。如果q=0，表示該物品為主件，如果q>0，表示該物品為附件，q是所屬主件的編號(hào)）

輸出格式OutputFormat輸出文件只有一個(gè)正整數(shù)，為不超過總錢數(shù)的物品的價(jià)格與重要度乘積的總和的最大值

（<200000）。樣例輸入SampleInput100058002040051300514003050020樣例輸出SampleOutput220048第四十八頁(yè)，共五十九頁(yè)，編輯于2023年，星期日例題9：石子歸并描述：在一個(gè)圓形操場(chǎng)的四周擺放著N堆石子(N<=

100),現(xiàn)要將石子有次序地合并成一堆.規(guī)定每次只能選取相鄰的兩堆合并成新的一堆,并將新的一堆的石子數(shù),記為該次合并的得分.編一程序,由文件讀入堆棧數(shù)N及每堆棧的石子數(shù)(<=20).

(!)選擇一種合并石子的方案,使用權(quán)得做N－1次合并,得分的總和最小;

(2)選擇一種合并石子的方案,使用權(quán)得做N－1次合并,得分的總和最小;

輸入數(shù)據(jù):

第一行為石子堆數(shù)N;

第二行為每堆的石子數(shù),每?jī)蓚€(gè)數(shù)之間用一個(gè)空格分隔.

輸出數(shù)據(jù):

從第一至第N行為得分最小的合并方案.第N+1行是空行.從第N+2行到第2N+1行是得分最大合并方案.每種合并方案用N行表示,其中第i行(1<=i<=N)表示第i次合并前各堆的石子數(shù)(依順時(shí)針次序輸出,哪一堆先輸出均可).要求將待合并的兩堆石子數(shù)以相應(yīng)的負(fù)數(shù)表示.

輸入輸出范例:

輸入:

4

4

5

9

4

輸出:

最小＝43最大＝5449第四十九頁(yè)，共五十九頁(yè)，編輯于2023年，星期日輸入:

4

4

5

9

4

輸出:

－４

５

９

－４

－８

－５

９

－１３

－９

２２４

－５

－９

４

４

－１４

－４

－４

－１８

２２拓：輸出合并的方案：50第五十頁(yè)，共五十九頁(yè)，編輯于2023年，星期日用〔i，j〕表示一個(gè)從第i堆數(shù)起，順時(shí)針數(shù)j堆時(shí)的子序列

｛第i堆、第i＋１堆、……、第（i＋j－1）modn堆｝步驟1f〔i，j〕──將子序列〔i，j〕中的j堆石子合并成一堆的最佳得分和；（結(jié)果數(shù)組）

c〔i，j〕──將〔i，j〕一分為二，其中子序列１的堆數(shù)；（記錄分隔點(diǎn)）打印合并方案時(shí)使用51第五十一頁(yè)，共五十九頁(yè)，編輯于2023年，星期日顯然，對(duì)每一堆石子來說，它的

f〔i，１〕＝０c〔i，１〕＝０（１≤i≤N）

對(duì)于子序列〔i，j〕來說，若求最小得分總和，f〔i，j〕的初始值為∞；若求最大得

分總和，f〔i，j〕的初始值為０。（１≤i≤N，２≤j≤N）。

規(guī)劃的方向是順推。先考慮含二堆石子的N個(gè)子序列（各子序列分別從第１堆、第２堆、

……、第N堆數(shù)起，順時(shí)針數(shù)２堆）的合并方案

f〔１，２〕，f〔２，２〕，……，f〔N，２〕

c〔１，２〕，c〔２，２〕，……，c〔N，２〕

然后考慮含三堆石子的Ｎ個(gè)子序列（各子序列分別從第１堆、第２堆、……、第Ｎ堆

數(shù)起，順時(shí)針數(shù)３堆）的合并方案

f〔１，３〕，f〔２，３〕，……，f〔N，３〕

c〔１，３〕，c〔２，３〕，……，c〔N，３〕

……

依次類推，直至考慮了含N堆石子的N個(gè)子序列（各子序列分別從第１堆、第２堆、…

…、第N堆數(shù)起，順時(shí)針數(shù)N堆）的合并方案

f〔１，N〕，f〔２，N〕，……，f〔N，N〕

c〔１，N〕，c〔２，N〕，……，c〔N，N〕

最后，在子序列〔１，N〕，〔２，N〕，……，〔N，N〕中，選擇得分總和（f值）最

?。ɑ蜃畲螅┑囊粋€(gè)子序列〔i，N〕（１≤i≤N），由此出發(fā)倒推合并過程。階段分析：52第五十二頁(yè)，共五十九頁(yè)，編輯于2023年，星期日例如對(duì)（圖6．2－4）中的６堆石子，按動(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〔６，４〕＝３

例題：３４６５４２53第五十三頁(yè)，共五十九頁(yè)，編輯于20