最優解問題中動態規劃的應用以及算法優化

周益民+陳艷碧

摘要：本文介紹了動態規劃的算法思想和實現步驟。以各類背包問題為例，闡述動態規劃的算法思想在最優解問題中的優勢，以及和其他算法之間的對比，并對傳統的動態規劃算法進行時間復雜度和空間復雜度上的優化。

1 動態規劃的基本原理

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

2 動態規劃的適用條件

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

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

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

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

3 動態規劃應用實例---背包問題

3.1 01背包問題

3.1.1 題目

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

3.1.2 基本思路

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

F[i，v]=max{F[i-1，v]，F[i-1，v-Ci]+Wi}

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

3.1.3 優化空間復雜度

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

3.1.4 初始化的細節問題

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

3.1.5 一個常數優化

上面偽代碼中的 for i ← 1 to N for v ← V to Ci

中第二重循環的下限可以改進。它可以被優化為

for i← 1 to N

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

3.1.6 小結

01背包問題是最基本的背包問題，它包含了背包問題中設計狀態、方程的最基本思 想。另外，別的類型的背包問題往往也可以轉換成01背包問題求解。故一定要仔細體會上面基本思路的得出方法，狀態轉移方程的意義，以及空間復雜度怎樣被優化。

4 結語

動態規劃的算法思想在解決類似背包問題的最優解問題中有很好的應用，我認為動態規劃的思想有別于其他分治方法的地方在于它是用于解決不連續、矢量化數據的首選。因為數據的不連續導致其他算法例如：分治算法、貪心算法都不能得到該種問題下的最優解。

參考文獻：

[1]傅清祥，王曉東，算法與數據結構，電子工業出版社，1998

[2]現代應用數學手冊——運籌學與最優化理論卷，清華大學出版社，1998

[3]來煜坤，把握本質，靈活運用——動態規劃的深入探討，中國NOI國家集訓隊論文集

[4]李剛，動態規劃的深入討論，中國NOI國家集訓隊論文集

作者簡介：

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

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