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

1、有8萬(wàn)元的投資可以投給3個(gè)過(guò)目，每個(gè)項(xiàng)目在不同筒子數(shù)額下（以萬(wàn)元為單位）的利潤(rùn)如下表投資額盈利項(xiàng)目012345678項(xiàng)目105154080909598100項(xiàng)目20515406070737475項(xiàng)目30426404550515253請(qǐng)安排投資計(jì)劃，使總的利潤(rùn)最大。寫(xiě)出你所設(shè)的狀態(tài)變量、決策變量、狀態(tài)轉(zhuǎn)移方程與遞推關(guān)系式和手工求解的詳細(xì)步驟及結(jié)構(gòu)。求解：狀態(tài)變量：xk 表示留給項(xiàng)目k.n的投資額，其中n為項(xiàng)目總個(gè)數(shù)，k=1.n.決策變量：uk 表示投給項(xiàng)目k的投資額.允許決策集合：Dkxk=uk | 0ukxk狀態(tài)轉(zhuǎn)移方程：xk+1=xk-uk遞推關(guān)系式：fkxk=ukDkxkmax gkuk+

2、fk+1xk-uk k=n-1,1fnxn=gnxn 其中，gkuk表示項(xiàng)目k的投資額為uk時(shí)的盈利.針對(duì)本題，n = 3，xk最大取8手工詳解過(guò)程：1. 初始化k = 3f30=0;f31=4;f32=26;f33=40;f34=45;f35=50;f36=51;f37=52;f38=53. x3012345678f3(x3)04264045505152532. k = 2f20=maxg20+f30=0+0=0;f21=maxg20+f31,g21+f30=max0+4,5+0=5;f22=maxg20+f32,g21+f31,g22+f30=max0+26,5+4,15+0=26;f23

3、=maxg20+f33,g21+f32,g22+f31,g23+f30=max0+40,5+26,15+4,40+0=40;f24=maxg20+f34,g21+f33,g22+f32,g23+f31,g24+f30=max0+45,5+40,15+26,40+4,60+0=60;f25=maxg20+f35,g21+f34,g22+f33,g23+f32,g24+f31,g25+f30=max0+50,5+45,15+40,40+26,60+4,70+0=70;f26=maxg20+f36,g21+f35,g22+f34,g23+f33,g24+f32,g25+f31,g26+f30=max

4、0+51,5+50,15+45,40+40,60+26,70+4,73+0=86;f27=maxg20+f37,g21+f36,g22+f35,g23+f34,g24+f33,g25+f32,g26+f31,g27+f30=max0+52,5+51,15+50,40+45,60+40,70+26,73+4,74+0=100;f28=maxg20+f38,g21+f37,g22+f36,g23+f35,g24+f34,g25+f33,g26+f32,g27+f31,g28+f30=max0+53,5+52,15+51,40+50,60+45,70+40,73+26,74+4,75+0=110.x

5、2012345678f2(x2)0526406070861001103. k = 1f18=maxg10+f28,g11+f27,g12+f26,g13+f25,g14+f24,g15+f23,g16+f22,g17+f21,g18+f20=max0+110,5+100,15+86,40+70,80+60,90+40,95+26,98+5,100+0=140x1012345678f1(x1)0526408090106120140最終結(jié)果：給項(xiàng)目1投資4萬(wàn)元，項(xiàng)目2投資4萬(wàn)元，項(xiàng)目3不投資，將獲得最大利潤(rùn)140萬(wàn)元.python實(shí)現(xiàn)自頂向下，自底向上常用的算法設(shè)計(jì)思想主要有動(dòng)態(tài)規(guī)劃、貪婪法、隨機(jī)

6、化算法、回溯法等等，這些思想有重疊的部分，當(dāng)面對(duì)一個(gè)問(wèn)題的時(shí)候，從這幾個(gè)思路入手往往都能得到一個(gè)還不錯(cuò)的答案。本來(lái)想把動(dòng)態(tài)規(guī)劃單獨(dú)拿出來(lái)寫(xiě)三篇文章呢，后來(lái)發(fā)現(xiàn)自己學(xué)疏才淺，實(shí)在是只能講一些皮毛，更深入的東西嘗試構(gòu)思了幾次，也沒(méi)有什么進(jìn)展，打算每種設(shè)計(jì)思想就寫(xiě)一篇吧。動(dòng)態(tài)規(guī)劃（Dynamic Programming）是一種非常有用的用來(lái)解決復(fù)雜問(wèn)題的算法，它通過(guò)把復(fù)雜問(wèn)題分解為簡(jiǎn)單的子問(wèn)題的方式來(lái)獲得最優(yōu)解。一、自頂向下和自底向上總體上來(lái)說(shuō)，我們可以把動(dòng)態(tài)規(guī)劃的解法分為自頂向下和自底向上兩種方式。一個(gè)問(wèn)題如果可以使用動(dòng)態(tài)規(guī)劃來(lái)解決，那么它必須具有“最優(yōu)子結(jié)構(gòu)”，簡(jiǎn)單來(lái)說(shuō)就是，如果該問(wèn)題可以被分解

7、為多個(gè)子問(wèn)題，并且這些子問(wèn)題有最優(yōu)解，那這個(gè)問(wèn)題才可以使用動(dòng)態(tài)規(guī)劃。自頂向下（Top-Down）自頂向下的方式其實(shí)就是使用遞歸來(lái)求解子問(wèn)題，最終解只需要調(diào)用遞歸式，子問(wèn)題逐步往下層遞歸的求解。我們可以使用緩存把每次求解出來(lái)的子問(wèn)題緩存起來(lái)，下次調(diào)用的時(shí)候就不必再遞歸計(jì)算了。舉例著名的斐波那契數(shù)列的計(jì)算：#!/usr/bin/env python# coding:utf-8def fib(number): if number = 0 or number = 1: return 1 else: return fib(number - 1) + fib(number - 2)if _name_ =

8、_main_: print fib(35)有一點(diǎn)開(kāi)發(fā)經(jīng)驗(yàn)的人就能看出，fib(number-1)和fib(number-2)會(huì)導(dǎo)致我們產(chǎn)生大量的重復(fù)計(jì)算，以上程序執(zhí)行了14s才出結(jié)果，現(xiàn)在，我們把每次計(jì)算出來(lái)的結(jié)果保存下來(lái)，下一次需要計(jì)算的時(shí)候直接取緩存，看看結(jié)果：#!/usr/bin/env python# coding:utf-8cache = def fib(number): if number in cache: return cachenumber if number = 0 or number = 1: return 1 else: cachenumber = fib(number

9、 - 1) + fib(number - 2) return cachenumberif _name_ = _main_: print fib(35)耗費(fèi)時(shí)間為 0m0.053s 效果提升非常明顯。自底向上（Bottom-Up）自底向上是另一種求解動(dòng)態(tài)規(guī)劃問(wèn)題的方法，它不使用遞歸式，而是直接使用循環(huán)來(lái)計(jì)算所有可能的結(jié)果，往上層逐漸累加子問(wèn)題的解。我們?cè)谇蠼庾訂?wèn)題的最優(yōu)解的同時(shí)，也相當(dāng)于是在求解整個(gè)問(wèn)題的最優(yōu)解。其中最難的部分是找到求解最終問(wèn)題的遞歸關(guān)系式，或者說(shuō)狀態(tài)轉(zhuǎn)移方程。這里舉一個(gè)01背包問(wèn)題的例子：你現(xiàn)在想買一大堆算法書(shū)，需要很多錢，所以你打算去搶一個(gè)商店，這個(gè)商店一共有n個(gè)商品。問(wèn)題在

10、于，你只能最多拿 W kg 的東西。wi和vi分別表示第i個(gè)商品的重量和價(jià)值。我們的目標(biāo)就是在能拿的下的情況下，獲得最大價(jià)值，求解哪些物品可以放進(jìn)背包。對(duì)于每一個(gè)商品你有兩個(gè)選擇：拿或者不拿。首先我們要做的就是要找到“子問(wèn)題”是什么，我們發(fā)現(xiàn)，每次背包新裝進(jìn)一個(gè)物品，就可以把剩余的承重能力作為一個(gè)新的背包來(lái)求解，一直遞推到承重為0的背包問(wèn)題：作為一個(gè)聰明的賊，你用mi,w表示偷到商品的總價(jià)值，其中i表示一共多少個(gè)商品，w表示總重量，所以求解mi,w就是我們的子問(wèn)題，那么你看到某一個(gè)商品i的時(shí)候，如何決定是不是要裝進(jìn)背包，有以下幾點(diǎn)考慮：1. 該物品的重量大于背包的總重量，不考慮，換下一個(gè)商品；

11、2. 該商品的重量小于背包的總重量，那么我們嘗試把它裝進(jìn)去，如果裝不下就把其他東西換出來(lái)，看看裝進(jìn)去后的總價(jià)值是不是更高了，否則還是按照之前的裝法；3. 極端情況，所有的物品都裝不下或者背包的承重能力為0，那么總價(jià)值都是0；由以上的分析，我們可以得出mi,w的狀態(tài)轉(zhuǎn)移方程為：有了狀態(tài)轉(zhuǎn)移方程，那么寫(xiě)起代碼來(lái)就非常簡(jiǎn)單了，首先看一下自頂向下的遞歸方式，比較容易理解：#!/usr/bin/env python# coding:utf-8cache = items = range(0,9)weights = 10,1,5,9,10,7,3,12,5values = 10,20,30,15,40,6,

12、9,12,18# 最大承重能力W = 4def m(i,w): if str(i)+,+str(w) in cache: return cachestr(i)+,+str(w) result = 0 # 特殊情況 if i = 0 or w = 0: return 0 # w wi if w = wi if w = weightsi: # 把第i個(gè)物品放入背包后的總價(jià)值 take_it = m(i-1,w - weightsi) + valuesi # 不把第i個(gè)物品放入背包的總價(jià)值 ignore_it = m(i-1,w) # 哪個(gè)策略總價(jià)值高用哪個(gè) result = max(take_it

13、,ignore_it) if take_it ignore_it: print take ,i else: print did not take,i cachestr(i)+,+str(w) = result return resultif _name_ = _main_: # 背包把所有東西都能裝進(jìn)去做假設(shè)開(kāi)始 print m(len(items)-1,W)改造成非遞歸，即循環(huán)的方式，從底向上求解：#!/usr/bin/env python# coding:utf-8cache = items = range(1,9)weights = 10,1,5,9,10,7,3,12,5values

14、= 10,20,30,15,40,6,9,12,18# 最大承重能力W = 4def knapsack(): for w in range(W+1): cacheget_key(0,w) = 0 for i in items: cacheget_key(i,0) = 0 for w in range(W+1): if w = weightsi: if cacheget_key(i-1,w-weightsi) + valuesi cacheget_key(i-1,w): cacheget_key(i,w) = valuesi + cacheget_key(i-1,w-weightsi) else

15、: cacheget_key(i,w) = cacheget_key(i-1,w) else: cacheget_key(i,w) = cacheget_key(i-1,w) return cacheget_key(8,W)def get_key(i,w): return str(i)+,+str(w)if _name_ = _main_: # 背包把所有東西都能裝進(jìn)去做假設(shè)開(kāi)始 print knapsack()從這里可以看出，其實(shí)很多動(dòng)態(tài)規(guī)劃問(wèn)題都可以使用循環(huán)替代遞歸求解，他們的區(qū)別在于，循環(huán)方式會(huì)窮舉出所有可能用到的數(shù)據(jù)，而遞歸只需要計(jì)算那些對(duì)最終解有幫助的子問(wèn)題的解，但是遞歸本身是很耗費(fèi)

16、性能的，所以具體實(shí)踐中怎么用要看具體問(wèn)題具體分析。最長(zhǎng)公共子序列（LCS）解決了01背包問(wèn)題之后，我們對(duì)“子問(wèn)題”和“狀態(tài)轉(zhuǎn)移方程”有了一點(diǎn)點(diǎn)理解，現(xiàn)在趁熱打鐵，來(lái)試試解決LCS問(wèn)題：字符串一“ABCDABCD”和字符串二”BDCFG”的公共子序列（不是公共子串，不需要連續(xù)）是BDC，現(xiàn)在給出兩個(gè)確定長(zhǎng)度的字符串X和Y，求他們的最大公共子序列的長(zhǎng)度。首先，我們還是找最優(yōu)子結(jié)構(gòu)，即把問(wèn)題分解為子問(wèn)題，X和Y的最大公共子序列可以分解為X的子串Xi和Y的子串Yj的最大公共子序列問(wèn)題。其次，我們需要考慮Xi和Yj的最大公共子序列Ci,j需要符合什么條件：1. 如果兩個(gè)串的長(zhǎng)度都為0，則公共子序列的長(zhǎng)度

17、也為0；2. 如果兩個(gè)串的長(zhǎng)度都大于0且最后面一位的字符相同，則公共子序列的長(zhǎng)度是Ci1,j1的長(zhǎng)度加一；3. 如果兩個(gè)子串的長(zhǎng)度都大于0，且最后面一位的字符不同，則最大公共子序列的長(zhǎng)度是Ci1,j和Ci,j1的最大值；最后，根據(jù)條件獲得狀態(tài)轉(zhuǎn)移函數(shù)：由此轉(zhuǎn)移函數(shù)，很容易寫(xiě)出遞歸代碼：#!/usr/bin/env python# coding:utf-8cache = # 為了下面表示方便更容易理解，數(shù)組從1開(kāi)始編號(hào)# 即當(dāng)i,j為0的時(shí)候，公共子序列為0，屬于極端情況A = 0,A,B,C,B,D,A,B,E,FB = 0,B,D,C,A,B,A,Fdef C(i,j): if get_ke

18、y(i,j) in cache: return cacheget_key(i,j) result = 0 if i 0 and j 0: if Ai = Bj: result = C(i-1,j-1)+1 else: result = max(C(i,j-1),C(i-1,j) cacheget_key(i,j) = result return resultdef get_key(i,j): return str(i)+,+str(j)if _name_ = _main_: print C(len(A)-1,len(B)-1)上面程序的輸出結(jié)果為5，我們也可以像背包問(wèn)題一樣，把上面代碼改造成自

19、底向上的求解方式，這里就省略了。但是實(shí)際應(yīng)用中，我們可能更需要求最大公共子序列的序列，而不只是序列的長(zhǎng)度，所以我們下面額外考慮一下如何輸出這個(gè)結(jié)果。其實(shí)輸出LCS字符串也是使用動(dòng)態(tài)規(guī)劃的方法，我們假設(shè)LCSi,j表示長(zhǎng)度為i的字符串和長(zhǎng)度為j的字符串的最大公共子序列，那么我們有以下?tīng)顟B(tài)轉(zhuǎn)移函數(shù)：其中Ci,j是我們之前求得的最大子序列長(zhǎng)度的緩存，根據(jù)上面的狀態(tài)轉(zhuǎn)移函數(shù)寫(xiě)出遞歸代碼并不麻煩：#!/usr/bin/python# coding:utf-8Dynamic ProgrammingCACHE = # 為了下面表示方便，數(shù)組從1開(kāi)始編號(hào)# 即當(dāng)i,j為0的時(shí)候，公共子序列為0，屬于極端情況A = 0, A, B, C, B, D, A, B, E, FB = 0, B, D, C, A, B, A, Fdef lcs_length(i, j): Calculate max sequence leng