動(dòng)態(tài)規(guī)劃例子

1、. -有 8 萬元的投資可以投給 投資額3 個(gè)過目,每個(gè)工程在不同筒子數(shù)額下以萬元為單位的利潤如下表盈利0 1 2 3 4 5 6 7 8 工程工程 1 0 5 15 40 80 90 95 98 100 工程 2 0 5 15 40 60 70 73 74 75 工程 3 0 4 26 40 45 50 51 52 53 請(qǐng)支配投資方案,使總的利潤最大；寫出你所設(shè)的狀態(tài)變量、決策變量、狀態(tài)轉(zhuǎn)移方程與遞推關(guān)系式和手工求解的具體步驟及構(gòu)造；求解：狀態(tài)變量：xk 表示留給工程 k.n 的投資額,其中 n 為工程總個(gè)數(shù), k=1.n. 決策變量： uk 表示投給工程 k 的投資額 . 答應(yīng)決策集合：

2、狀態(tài)轉(zhuǎn)移方程：遞推關(guān)系式：其中,表示工程 k 的投資額為 uk 時(shí)的盈利 . 針對(duì)此題, n = 3,xk 最大取 8 手工詳解過程：1.初始化 k = 3 .word.zl- x3. 0 1 2 3 4 5 6 7 -8 f3x3 0 4 26 40 45 50 51 52 53 2.k = 2 - .word.zlx2. 0 1 2 3 4 5 6 7 -8 f2x2 0 5 26 40 60 70 86 100 110 3.k = 1 x10 1 2 3 4 5 6 7 8 f1x1 0 5 26 40 80 90 106 120 140 最終結(jié)果： 給工程 1 投資 4 萬元,工程 2

3、 投資 4 萬元,工程 3 不投資,將獲得最大利潤 140萬元. python 實(shí)現(xiàn)自頂向下,自底向上常用的算法設(shè)計(jì)思想主要有動(dòng)態(tài)規(guī)劃、貪婪法、隨機(jī)化算法、回溯法等等,這些思想有 重疊的局部,當(dāng)面對(duì)一個(gè)問題的時(shí)候,從這幾個(gè)思路入手往往都能得到一個(gè)仍不錯(cuò)的答案；原來想把動(dòng)態(tài)規(guī)劃單獨(dú)拿出來寫三篇文章呢,后來發(fā)覺自己學(xué)疏才淺,實(shí)在是只能講一些皮毛,更深化的東西嘗試構(gòu)思了幾次,也沒有什么進(jìn)展,準(zhǔn)備每種設(shè)計(jì)思想就寫一篇吧；動(dòng)態(tài)規(guī)劃 Dynamic Programming是一種特別有用的用來解決復(fù)雜問題的算法,它通過把 復(fù)雜問題分解為簡潔的子問題的方式來獲得最優(yōu)解；一、自頂向下和自底向上總體上來說,我們可

4、以把動(dòng)態(tài)規(guī)劃的解法分為自頂向下和自底向上兩種方式；- .word.zl. -一個(gè)問題假如可以使用動(dòng)態(tài)規(guī)劃來解決,那么它必需具有“ 最優(yōu)子構(gòu)造,簡潔來說就是,假如該問題可以被分解為多個(gè)子問題,并且這些子問題有最優(yōu)解,那這個(gè)問題才可以使用動(dòng)態(tài)規(guī)劃；自頂向下 Top-Down 自頂向下的方式其實(shí)就是使用遞歸來求解子問題,最終解只需要調(diào)用遞歸式,子問題逐步往 下層遞歸的求解； 我們可以使用緩存把每次求解出來的子問題緩存起來,下次調(diào)用的時(shí)候就 不必再遞歸運(yùn)算了；舉例聞名的斐波那契數(shù)列的運(yùn)算：#./usr/bin/env python # coding:utf-8 deffibnumber: ifnumb

5、er= 0ornumber= 1: return1 else: returnfibnumber-1+fibnumber-2 if_name_= _main_: printfib35 有一點(diǎn)開發(fā)經(jīng)受的人就能看出,fibnumber-1 和 fibnumber-2會(huì)導(dǎo)致我們產(chǎn)生大量的重復(fù)計(jì)算,以上程序執(zhí)行了 14s 才出結(jié)果,現(xiàn)在,我們把每次運(yùn)算出來的結(jié)果儲(chǔ)存下來,下一次需 要運(yùn)算的時(shí)候直接取緩存,看看結(jié)果：#./usr/bin/env python # coding:utf-8 cache= deffibnumber: - .word.zl. -ifnumberincache: returnca

6、chenumber ifnumber= 0ornumber= 1: return1 else: cachenumber= fibnumber-1+ fibnumber-2 returncachenumber if_name_= _main_: printfib35 消耗時(shí)間為 0m0.053s 成效提升特別明顯；自底向上 Bottom-Up 自底向上是另一種求解動(dòng)態(tài)規(guī)劃問題的方法,有可能的結(jié)果,往上層逐步累加子問題的解；它不使用遞歸式, 而是直接使用循環(huán)來運(yùn)算所我們?cè)谇蠼庾訂栴}的最優(yōu)解的同時(shí),也相當(dāng)于是在求解整個(gè)問題的最優(yōu)解；其中最難的局部是找到求解最終問題的遞歸關(guān)系式,或者說狀態(tài)轉(zhuǎn)移方程；這

7、里舉一個(gè) 01 背包問題的例子：你現(xiàn)在想買一大堆算法書,需要許多錢, 所以你準(zhǔn)備去搶一個(gè)商店,這個(gè)商店一共有 n 個(gè)商品；問題在于,你只能最多拿 W kg 的東西； wi 和 vi 分別表示第 i 個(gè)商品的重量和價(jià)值；我們的目標(biāo)就是在能拿的下的情形下,獲得最大價(jià)值, 求解哪些物品可以放進(jìn)背包；對(duì)于每一個(gè)商品你有兩個(gè)挑選：拿或者不拿；第一我們要做的就是要找到“ 子問題是什么,我們發(fā)覺,每次背包新裝進(jìn)一個(gè)物品,就可以把剩余的承重才能作為一個(gè)新的背包來求解,始終遞推到承重為0 的背包問題：作為一個(gè)聰慧的賊,你用 mi,w表示偷到商品的總價(jià)值,其中 i 表示一共多少個(gè)商品,w 表示總重量,所以求解 m

8、i,w就是我們的子問題,那么你看到某一個(gè)商品 i 的時(shí)候,如何打算- .word.zl. -是不是要裝進(jìn)背包,有以下幾點(diǎn)考慮：1. 該物品的重量大于背包的總重量,不考慮,換下一個(gè)商品；2. 該商品的重量小于背包的總重量,那么我們嘗試把它裝進(jìn)去,假如裝不下就把其他東西換出來,看看裝進(jìn)去后的總價(jià)值是不是更高了,否那么仍是依據(jù)之前的裝法；3.極端情形,全部的物品都裝不下或者背包的承重才能為0,那么總價(jià)值都是0；由以上的分析,我們可以得出mi,w 的狀態(tài)轉(zhuǎn)移方程為：有了狀態(tài)轉(zhuǎn)移方程,那么寫起代碼來就特別簡潔了,第一看一下自頂向下的遞歸方式,比較簡潔懂得：#./usr/bin/env python #

9、coding:utf-8 cache= items=range0,9 weights=10,1,5,9,10,7,3,12,5 values=10,20,30,15,40,6,9,12,18 # 最大承重才能 W=4 defmi,w: ifstri+,+strwincache: returncachestri+,+strw result=0 - .word.zl. -# 特別情形 ifi= 0orw= 0: return0 # w wi ifw= wi ifw= weightsi: # 把第 i 個(gè)物品放入背包后的總價(jià)值 take_it=mi-1,w-weightsi+valuesi # 不把

10、第 i 個(gè)物品放入背包的總價(jià)值 ignore_it=mi-1,w # 哪個(gè)策略總價(jià)值高用哪個(gè) result=maxtake_it,ignore_it iftake_itignore_it: printtake ,i else: printdid not take,i cachestri+,+strw=result returnresult if_name_= _main_: # 背包把全部東西都能裝進(jìn)去做假設(shè)開場- .word.zl. -printmlenitems-1,W 改造成非遞歸,即循環(huán)的方式,從底向上求解：#./usr/bin/env python # coding:utf-8 ca

11、che= items=range1,9 weights=10,1,5,9,10,7,3,12,5 values=10,20,30,15,40,6,9,12,18 # 最大承重才能 W=4 defknapsack: forwinrangeW+1: cacheget_key0,w=0 foriinitems: cacheget_keyi,0=0 forwinrangeW+1: ifw= weightsi: ifcacheget_keyi-1,w-weightsi+valuesicacheget_keyi-1,w: cacheget_keyi,w=valuesi+cacheget_keyi-1,w-

12、weightsi else: cacheget_keyi,w=cacheget_keyi-1,w else: - .word.zl. -cacheget_keyi,w=cacheget_keyi-1,w returncacheget_key8,W defget_keyi,w: returnstri+,+strw if_name_= _main_: # 背包把全部東西都能裝進(jìn)去做假設(shè)開場 printknapsack 從這里可以看出,其實(shí)許多動(dòng)態(tài)規(guī)劃問題都可以使用循環(huán)替代遞歸求解,他們的區(qū)分在于,循環(huán)方式會(huì)窮舉出全部可能用到的數(shù)據(jù),而遞歸只需要運(yùn)算那些對(duì)最終解有幫忙的子問題的 解,但是遞歸本身是很

13、消耗性能的,所以具體實(shí)踐中怎么用要看具體問題具體分析；最長公共子序列 LCS解決了 01 背包問題之后,我們對(duì)“ 子問題和“ 狀態(tài)轉(zhuǎn)移方程有了一點(diǎn)點(diǎn)懂得,現(xiàn)在趁 熱打鐵,來試試解決 LCS 問題：字符串一“ABCDABCD 和字符串二BDCFG 的公共子序列不是公共子串,不需要連續(xù)是 BDC ,現(xiàn)在給出兩個(gè)確定長度的字符串X 和 Y,求他們的最大公共子序列的長度；第一,我們?nèi)允钦易顑?yōu)子構(gòu)造,即把問題分解為子問題,X 和 Y 的最大公共子序列可以分解為 X 的子串 Xi 和 Y 的子串 Yj 的最大公共子序列問題；其次,我們需要考慮 Xi 和 Yj 的最大公共子序列 Ci,j 需要符合什么條件：

14、1. 假如兩個(gè)串的長度都為 0,那么公共子序列的長度也為 0；2. 假如兩個(gè)串的長度都大于 0 且最終面一位的字符一樣,那么公共子序列的長度是 Ci- 1,j- 1的長度加一；3.假如兩個(gè)子串的長度都大于0,且最終面一位的字符不同,那么最大公共子序列的長度是 Ci- 1,j和 Ci,j- 1的最大值；- .word.zl. -最終,依據(jù)條件獲得狀態(tài)轉(zhuǎn)移函數(shù)：由此轉(zhuǎn)移函數(shù),很簡潔寫出遞歸代碼：#./usr/bin/env python # coding:utf-8 cache= # 為了下面表示便利更簡潔懂得,數(shù)組從 1 開場編號(hào) # 即當(dāng) i,j 為 0 的時(shí)候,公共子序列為 0,屬于極端情形

15、 A=0,A,B,C,B,D,A,B,E,F B=0,B,D,C,A,B,A,F defCi,j: ifget_keyi,jincache: returncacheget_keyi,j result=0 ifi0andj0: ifAi= Bj: result=Ci-1,j-1+1 else: result=maxCi,j-1,Ci-1,j - .word.zl. -cacheget_keyi,j=result returnresult defget_keyi,j: returnstri+,+strj if_name_= _main_: printClenA-1,lenB-1 上面程序的輸出結(jié)果

16、為 5,我們也可以像背包問題一樣,把上面代碼改造成自底向上的求解 方式,這里就省略了；但是實(shí)際應(yīng)用中, 我們可能更需要求最大公共子序列的序列,而不只是序列的長度,所以我們下面額外考慮一下如何輸出這個(gè)結(jié)果；其實(shí)輸出LCS 字符串也是使用動(dòng)態(tài)規(guī)劃的方法,我們假設(shè)LCSi,j表示長度為i 的字符串和長度為 j 的字符串的最大公共子序列,那么我們有以下狀態(tài)轉(zhuǎn)移函數(shù)：其中 Ci,j是我們之前求得的最大子序列長度的緩存,依據(jù)上面的狀態(tài)轉(zhuǎn)移函數(shù)寫出遞歸代 碼并不麻煩：#./usr/bin/python # coding:utf-8Dynamic Programming CACHE= # 為了下面表示便利,數(shù)

17、組從1 開場編號(hào).word.zl- . 0,屬于極端情形-# 即當(dāng) i,j 為 0 的時(shí)候,公共子序列為A=0,A,B,C,B,D,A,B,E,F B=0,B,D,C,A,B,A,F deflcs_lengthi,j: Calculate max sequence length ifget_keyi,jinCACHE: returnCACHEget_keyi,j result=0 ifi0andj0: ifAi= Bj: result=lcs_lengthi-1,j-1+1 else: result=maxlcs_lengthi,j-1,lcs_lengthi-1,j CACHEget_keyi,j=result returnresult deflcsi,j: backtrack lcs ifi= 0orj= 0: return ifAi= Bj: returnlcsi-1,j-1+Ai else: - .word.zl. -ifCACHEget