1、. -有 8 萬元的投資可以投給 投資額3 個過目,每個工程在不同筒子數額下以萬元為單位的利潤如下表盈利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 請支配投資方案,使總的利潤最大；寫出你所設的狀態變量、決策變量、狀態轉移方程與遞推關系式和手工求解的具體步驟及構造；求解：狀態變量：xk 表示留給工程 k.n 的投資額,其中 n 為工程總個數, k=1.n. 決策變量： uk 表示投給工程 k 的投資額 . 答應決策集合：

2、狀態轉移方程：遞推關系式：其中,表示工程 k 的投資額為 uk 時的盈利 . 針對此題, 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 最終結果： 給工程 1 投資 4 萬元,工程 2

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

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

5、er= 0ornumber= 1: return1 else: returnfibnumber-1+fibnumber-2 if_name_= _main_: printfib35 有一點開發經受的人就能看出,fibnumber-1 和 fibnumber-2會導致我們產生大量的重復計算,以上程序執行了 14s 才出結果,現在,我們把每次運算出來的結果儲存下來,下一次需 要運算的時候直接取緩存,看看結果：#./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 消耗時間為 0m0.053s 成效提升特別明顯；自底向上 Bottom-Up 自底向上是另一種求解動態規劃問題的方法,有可能的結果,往上層逐步累加子問題的解；它不使用遞歸式, 而是直接使用循環來運算所我們在求解子問題的最優解的同時,也相當于是在求解整個問題的最優解；其中最難的局部是找到求解最終問題的遞歸關系式,或者說狀態轉移方程；這

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

8、i,w就是我們的子問題,那么你看到某一個商品 i 的時候,如何打算- .word.zl. -是不是要裝進背包,有以下幾點考慮：1. 該物品的重量大于背包的總重量,不考慮,換下一個商品；2. 該商品的重量小于背包的總重量,那么我們嘗試把它裝進去,假如裝不下就把其他東西換出來,看看裝進去后的總價值是不是更高了,否那么仍是依據之前的裝法；3.極端情形,全部的物品都裝不下或者背包的承重才能為0,那么總價值都是0；由以上的分析,我們可以得出mi,w 的狀態轉移方程為：有了狀態轉移方程,那么寫起代碼來就特別簡潔了,第一看一下自頂向下的遞歸方式,比較簡潔懂得：#./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 個物品放入背包后的總價值 take_it=mi-1,w-weightsi+valuesi # 不把

10、第 i 個物品放入背包的總價值 ignore_it=mi-1,w # 哪個策略總價值高用哪個 result=maxtake_it,ignore_it iftake_itignore_it: printtake ,i else: printdid not take,i cachestri+,+strw=result returnresult if_name_= _main_: # 背包把全部東西都能裝進去做假設開場- .word.zl. -printmlenitems-1,W 改造成非遞歸,即循環的方式,從底向上求解：#./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_: # 背包把全部東西都能裝進去做假設開場 printknapsack 從這里可以看出,其實許多動態規劃問題都可以使用循環替代遞歸求解,他們的區分在于,循環方式會窮舉出全部可能用到的數據,而遞歸只需要運算那些對最終解有幫忙的子問題的 解,但是遞歸本身是很

13、消耗性能的,所以具體實踐中怎么用要看具體問題具體分析；最長公共子序列 LCS解決了 01 背包問題之后,我們對“ 子問題和“ 狀態轉移方程有了一點點懂得,現在趁 熱打鐵,來試試解決 LCS 問題：字符串一“ABCDABCD 和字符串二BDCFG 的公共子序列不是公共子串,不需要連續是 BDC ,現在給出兩個確定長度的字符串X 和 Y,求他們的最大公共子序列的長度；第一,我們仍是找最優子構造,即把問題分解為子問題,X 和 Y 的最大公共子序列可以分解為 X 的子串 Xi 和 Y 的子串 Yj 的最大公共子序列問題；其次,我們需要考慮 Xi 和 Yj 的最大公共子序列 Ci,j 需要符合什么條件：

14、1. 假如兩個串的長度都為 0,那么公共子序列的長度也為 0；2. 假如兩個串的長度都大于 0 且最終面一位的字符一樣,那么公共子序列的長度是 Ci- 1,j- 1的長度加一；3.假如兩個子串的長度都大于0,且最終面一位的字符不同,那么最大公共子序列的長度是 Ci- 1,j和 Ci,j- 1的最大值；- .word.zl. -最終,依據條件獲得狀態轉移函數：由此轉移函數,很簡潔寫出遞歸代碼：#./usr/bin/env python # coding:utf-8 cache= # 為了下面表示便利更簡潔懂得,數組從 1 開場編號 # 即當 i,j 為 0 的時候,公共子序列為 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 上面程序的輸出結果

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

17、組從1 開場編號.word.zl- . 0,屬于極端情形-# 即當 i,j 為 0 的時候,公共子序列為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