周益民+陳艷碧

摘要：本文介紹了動態(tài)規(guī)劃的算法思想和實現(xiàn)步驟。以各類背包問題為例，闡述動態(tài)規(guī)劃的算法思想在最優(yōu)解問題中的優(yōu)勢，以及和其他算法之間的對比，并對傳統(tǒng)的動態(tài)規(guī)劃算法進行時間復(fù)雜度和空間復(fù)雜度上的優(yōu)化。

1 動態(tài)規(guī)劃的基本原理

動態(tài)規(guī)劃算法通常用于求解具有某種最優(yōu)性質(zhì)的問題。在這類問題中，可能會有許多可行解。每一個解都對應(yīng)于一個值，我們希望找到具有最優(yōu)值的解。動態(tài)規(guī)劃算法與分治法類似，其基本思想也是將待求解問題分解成若干個子問題，先求解子問題，然后從這些子問題的解得到原問題的解。與分治法不同的是，適合于用動態(tài)規(guī)劃求解的問題，經(jīng)分解得到子問題往往不是互相獨立的。若用分治法來解這類問題，則分解得到的子問題數(shù)目太多，有些子問題被重復(fù)計算了很多次。如果我們能夠保存已解決的子問題的答案，而在需要時再找出已求得的答案，這樣就可以避免大量的重復(fù)計算，節(jié)省時間。我們可以用一個表來記錄所有已解的子問題的答案。不管該子問題以后是否被用到，只要它被計算過，就將其結(jié)果填入表中。這就是動態(tài)規(guī)劃法的基本思路。具體的動態(tài)規(guī)劃算法多種多樣，但它們具有相同的填表格式。

2 動態(tài)規(guī)劃的適用條件

任何思想方法都有一定的局限性，超出了特定條件，它就失去了作用。同樣，動態(tài)規(guī)劃也并不是萬能的。適用動態(tài)規(guī)劃的問題必須滿足最優(yōu)化原理和無后效性。

a.最優(yōu)化原理（最優(yōu)子結(jié)構(gòu)性質(zhì)）最優(yōu)化原理可這樣闡述：一個最優(yōu)化策略具有這樣的性質(zhì)，不論過去狀態(tài)和決策如何，對前面的決策所形成的狀態(tài)而言，余下的諸決策必須構(gòu)成最優(yōu)策略。簡而言之，一個最優(yōu)化策略的子策略總是最優(yōu)的。一個問題滿足最優(yōu)化原理又稱其具有最優(yōu)子結(jié)構(gòu)性質(zhì)。

b.無后效性將各階段按照一定的次序排列好之后，對于某個給定的階段狀態(tài)，它以前各階段的狀態(tài)無法直接影響它未來的決策，而只能通過當(dāng)前的這個狀態(tài)。換句話說，每個狀態(tài)都是過去歷史的一個完整總結(jié)。這就是無后向性，又稱為無后效性。

c.子問題的重疊性 動態(tài)規(guī)劃將原來具有指數(shù)級時間復(fù)雜度的搜索算法改進成了具有多項式時間復(fù)雜度的算法。其中的關(guān)鍵在于解決冗余，這是動態(tài)規(guī)劃算法的根本目的。動態(tài)規(guī)劃實質(zhì)上是一種以空間換時間的技術(shù)，它在實現(xiàn)的過程中，不得不存儲產(chǎn)生過程中的各種狀態(tài)，所以它的空間復(fù)雜度要大于其它的算法。

3 動態(tài)規(guī)劃應(yīng)用實例---背包問題

3.1 01背包問題

3.1.1 題目

有N件物品和一個容量為V的背包。放入第i件物品耗費的費用是 Ci1得到的價值是Wi。求解將哪些物品裝入背包可使價值總和最大。

3.1.2 基本思路

這是最基礎(chǔ)的背包問題，特點是：每種物品僅有一件，可以選擇放或不放。用子問題定義狀態(tài)：即F[i，v]表示前i件物品恰放入一個容量為v的背包可以獲得的最大價值。則其狀態(tài)轉(zhuǎn)移方程便是：

F[i，v]=max{F[i-1，v]，F(xiàn)[i-1，v-Ci]+Wi}

這個方程非常重要，基本上所有跟背包相關(guān)的問題的方程都是由它衍生出來的。所以有必要將它詳細(xì)解釋一下：“將前i件物品放入容量為 v的背包中”這個子問題，若只考慮第i件物品的策略（放或不放），那么就可以轉(zhuǎn)化為一個只和前i-1件物品相關(guān)的問題。如果不放第i件物品，那么問題就轉(zhuǎn)化為“前i-1件物品放入容量為v的背包中”，價值為F[i-1，v]；如果放第i件物品，那么問題就轉(zhuǎn)化為“前i-1件物品放入剩下的容量為v-Ci的背包中”，此時能獲得的最大價值就是F[i-1，v-Ci]再加上通過放入第i件物品獲得的價值Wi。

3.1.3 優(yōu)化空間復(fù)雜度

以上方法的時間和空間復(fù)雜度均為O（V N），其中時間復(fù)雜度應(yīng)該已經(jīng)不能再優(yōu)化了，但空間復(fù)雜度卻可以優(yōu)化到O（V）。先考慮上面講的基本思路如何實現(xiàn)，肯定是有一個主循環(huán)i←1...N，每次算出來二維數(shù)組F[i，0...V]的所有值。那么，如果只用一個數(shù)組F[0...V]，能不能保證第i次循環(huán)結(jié)束后F[v]中表示的就是我們定義的狀態(tài)F[i，v]呢？F[i，v]是由F[i-1，v]和F[i-1，v-Ci]兩個子問題遞推而來，能否保證在推F[i，v] 時（也即在第i次主循環(huán)中推F[v]時）能夠取用F[i-1，v]和F[i-1，v-Ci] 的值呢？事實上，這要求在每次主循環(huán)中我們以v←V...0的遞減順序計算F[v]，這樣才能保證計算F[v]時F[v-Ci]保存的是狀態(tài)F[i-1，v-Ci] 的值。

3.1.4 初始化的細(xì)節(jié)問題

我們看到的求最優(yōu)解的背包問題題目中，事實上有兩種不太相同的問法。有的題目要求“恰好裝滿背包”時的最優(yōu)解，有的題目則并沒有要求必須把背包裝滿。一種區(qū)別這兩種問法的實現(xiàn)方法是在初始化的時候有所不同。如果是第一種問法，要求恰好裝滿背包。那么在初始化時除了F[0]為0，其它F[1..V]均設(shè)為-∞，這樣就可以保證最終得到的F[V] 是一種恰好裝滿背包的最優(yōu)解。如果并沒有要求必須把背包裝滿，而是只希望價格盡量大，初始化時應(yīng)該將F[0..V]全部設(shè)為0。這是為什么呢？可以這樣理解：初始化的F數(shù)組事實上就是在沒有任何物品可以放入背包時的合法狀態(tài)。如果要求背包恰好裝滿，那么此時只有容量為0的背包可以在什么也不裝且價值為0的情況下被“恰好裝滿”，其它容量的背包均沒有合法的解，屬于未定義的狀態(tài)，應(yīng)該被賦值為-∞了。如果背包并非必須被裝滿，那么任何容量的背包 都有一個合法解“什么都不裝”，這個解的價值為0，所以初始時狀態(tài)的值也就全部為0了。這個小技巧完全可以推廣到其它類型的背包問題，后面不再對進行狀態(tài)轉(zhuǎn)移之前的初始化進行講解。

3.1.5 一個常數(shù)優(yōu)化

上面?zhèn)未a中的 for i ← 1 to N for v ← V to Ci

中第二重循環(huán)的下限可以改進。它可以被優(yōu)化為

for i← 1 to N

for v ← V to max（V -ΣN iWi，Ci）

3.1.6 小結(jié)

01背包問題是最基本的背包問題，它包含了背包問題中設(shè)計狀態(tài)、方程的最基本思 想。另外，別的類型的背包問題往往也可以轉(zhuǎn)換成01背包問題求解。故一定要仔細(xì)體會上面基本思路的得出方法，狀態(tài)轉(zhuǎn)移方程的意義，以及空間復(fù)雜度怎樣被優(yōu)化。

4 結(jié)語

動態(tài)規(guī)劃的算法思想在解決類似背包問題的最優(yōu)解問題中有很好的應(yīng)用，我認(rèn)為動態(tài)規(guī)劃的思想有別于其他分治方法的地方在于它是用于解決不連續(xù)、矢量化數(shù)據(jù)的首選。因為數(shù)據(jù)的不連續(xù)導(dǎo)致其他算法例如：分治算法、貪心算法都不能得到該種問題下的最優(yōu)解。

參考文獻：

[1]傅清祥，王曉東，算法與數(shù)據(jù)結(jié)構(gòu)，電子工業(yè)出版社，1998

[2]現(xiàn)代應(yīng)用數(shù)學(xué)手冊——運籌學(xué)與最優(yōu)化理論卷，清華大學(xué)出版社，1998

[3]來煜坤，把握本質(zhì)，靈活運用——動態(tài)規(guī)劃的深入探討，中國NOI國家集訓(xùn)隊論文集

[4]李剛，動態(tài)規(guī)劃的深入討論，中國NOI國家集訓(xùn)隊論文集

作者簡介：

周益民（1996.01.22-）男，漢族，身份證號：500224199601220035，本科生，重慶銅梁，研究方向：地理信息科學(xué)

陳艷碧（1996.02.16-）女，漢族，身份證號：530323199602160104，本科生，云南曲靖，研究方向：地理信息科學(xué)endprint