動態規劃法的應用分析

李小蓮

摘? 要： 闡述動態規劃法的基本原理及其求解方法、求解步驟，分析動態規劃法在生產生活中的應用，列舉了用動態規劃法求解多段圖的最短路徑問題、資源分配問題和0-1背包問題。通過對不同實例的求解，分析動態規劃法的不同計算思路，從而總結出動態規劃法的優點。

關鍵詞： 動態規劃; 最短路徑; 資源分配; 0-1背包

中圖分類號：TP301.6? ? ? ? ? 文獻標志碼：A? ? ?文章編號：1006-8228（2019）06-53-03

Abstract： This paper describes the basic principle of dynamic programming method， the method and procedure for solving， and analyses the application of dynamic programming method in production and life. How to use the dynamic programming method to solve the problems of shortest path，resource allocation and 0-1 Knapsack are enumerated. By solving different examples， the different calculation ideas of dynamic programming method are analyses， and the advantages are summarized.

Key words： dynamic programming; shortest path; resource allocation; 0-1 Knapsack

0 引言

動態規劃法是運籌學的一個重要分支，也是計算機學里的一種重要的計算方法。動態規劃法將一個復雜的多階段決策問題轉換為一系列的單個階段的問題，利用各階段之間的關系逐個求解。動態規劃法通常基于一個遞推公式及一個或多個初始狀態，當前子問題的解由上次子問題的解推出，它是以犧牲存儲空間換取計算時間的一種計算方法。

1 基本原理

動態規劃法的基本思想是將問題分解成若干互相關聯的階段，將各階段按一定的順序排列。構造狀態轉移方程分別求出每個階段的子問題的解，然后從子問題的解中采取自頂向下或自底向上的方式推出原問題的解。解決第一階段的問題，依賴于解決第二階段的子問題，解決第二階段問題又依賴于解決第三階段的子問題，如此類推下去直到得到原問題的解為止[1]。

2 解動態規劃法的基本方法

動態規劃有線性的、樹型的、背包類的，不同的問題類型采用的算法并不一致，但解決問題的思路都是一樣的，都需要把問題分為多個階段來處理。

2.1 解題思路

動態規劃所處理的問題是一個多階段決策問題，一般由初始狀態開始，通過對中間階段決策的選擇，達到結束狀態。這些決策形成了一個決策序列，同時確定了完成整個過程的一條活動路線，如圖1所示[2]。

2.2 解題步驟

用動態規劃法解決問題可以分為以下幾個步驟。

⑴ 按照問題的時間或空間特征把問題分為若干個階段。劃分后的階段是有序的或可排序。

⑵ 將問題發展到各個階段時所處的各種客觀情況用不同的狀態表示出來，狀態的選擇需要滿足無后效性。

⑶ 根據相鄰兩個階段的狀態關系來確定決策方法和狀態轉移方程。給出的狀態方程需是一個遞推式的方程，且給狀態方程設置一個終止條件或邊界條件[3]。

⑷ 根據狀態方程計算出各階段的最優解。

⑸ 根據計算的各階段的最優值信息構造出原問題的最優解。

3 動態規劃法的應用

動態規劃法的應用比較廣泛，常用的有多段圖的最短路徑、資源分配問題、會議安排問題、背包問題、設備更新、最長公共子序列等，下面將分析幾個應用方面的問題。

3.1 多段圖的最短路徑問題

多段圖的最短路徑問題是求從源點到終點的最短路徑或者最小費用的通路，設置數組元素c[][]：存儲邊的長度，pre[]表示最短路徑上當前頂點的前驅頂點，設置對應的狀態方程：f（s）=min{f（t）+c（t，s）}[4]。

如圖2，A處是一電力站，現在需要從A地架電線到E地，其中途徑B、C、D三地。邊上的數字表示與其相連的兩地間所需架設的電線的長度。求從A地到E地所需電線的長度的最小值。

采用順序解法，從源點出發，求到達當前狀態的最短路徑，然后再加入下一階段計算，直到終點。這里分為A、B、C、D、E五個階段，詳細計算如下。

3.2 資源分配問題

資源分配問題是對一定數目的資源進行合理分配后能夠得到最大價值的問題。假設某公司共有5個新增資源，欲分配給其下屬的三家子公司，各子公司得到新資源后每年的盈利情況如表1所示。表1顯示的是：分配給各子公司的資源數目是多少才能使整個公司盈利最大。

采用動態規劃方法，用字母i表示子公司的編號，子公司A、B、C對應編號分別為1、2、3，資源總數為n=5，子公司總數m=3。設置二位動態規劃數組d，d[i][s]表示子公司i～m共分配s個資源后能獲得的最大盈利，例如：d[2][4]表示子公司2～3共分配4個資源后能獲得的最大盈利，即公司B和C一起共分配4個資源后得到的最大盈利。再設置二位數組p[i][s]，表示求出d[i][s]對應子公司分配到的資源數。例如：p[2][4]表示求出d[2][4]時對應子公司2（子公司B）得到的資源數目。

確實好狀態和狀態變量，設置邊界條件dp[m+1][j]=0寫出對應的狀態轉移方程如下：

根據狀態方程計算最優解，計算過程如下：

顯然，d[4][*]=0（邊界條件），

接下來，通過p反推各個子公司的分配資源數。p[1][5]=2，子公司A分配資源數為2，余下資源為3;p[2][3]=2，子公司B分配資源數為2，余下資源為1;p[3][1]=1，子公司C分配資源數為1，余下資源為0。最大盈利為6+8+6=20。

3.3 0-1背包問題

設背包的總重量為W，物品的重量為wi，價值為vi，且W、wi、vi都為整數，即討論關于整數的背包問題。設置二位數組dp用來保存物品的最優解，dp[i][r]表示背包剩余容量為r時，已考慮物品1～i時背包的最大價值。xi表示物品的選取與否，按i=1，2，3，…，n的次序來確定xi的值。xi分為兩種狀態：

xi=0? 表示物品i不裝入背包中，

xi=1? 表示物品i裝入背包中。

0-1背包問題的狀態轉移方程如下[5]：

其中r=0，表示背包還能裝入0個物品;i=0，表示沒有任何物品可裝入背包;i>0，r>0且r0，r>0且w[i]?r時，在放入與不放之間選價值最優值。

請看下面實例分析：

有一個背包可容納W=10，現有4個物品，重量記為wi={2，2，5，3}，價值為vi={3，4，3，2}，每個物品都不能拆分，只能選擇放入或不放入，請用動態規劃法求解如何選擇裝入背包的物品，使背包中物品總價值最大。

根據狀態方程求得的dp數組以及求解過程如表2所示，其中數字右邊中括號里面0表示不選取該行所對應物品，1表示選取該行所對應物品。

4 總結

動態規劃，是求解問題的一種方法，它不是一種確定的算法，有多種類型的問題都可以用動態規劃的思路來解，只要滿足最優性原理、無后效性、有重疊子問題這三個性質，就可以用動態規劃法求解。本文詳細分析了動態規劃方法在最短路徑問題、資源分配問題、0-1背包問題等方面的應用，通過不同的應用實例，分析動態規劃的解題思路，高效率地得到更完整的解信息。所有動態規劃法對不同問題的解題算法也不盡相同。主要是先要確定好階段，每個階段的選擇都很重要，先對子問題求出最優解，從而得出原問題的最優解。后續將更深入研究動態規劃法在其他方面的應用。

參考文獻（References）：

[1] 張愛華，郭喜躍，陳前軍.動態規劃算法分析與研究[J].軟件導刊，2014.12：68-69

[2] 趙娟，樊超.動態規劃方法的應用研究[J].計算機時代，2014.2：28-30.

[3] 呂國英，李茹等.算法設計與分析（第3版）[M].清華大學出版社，2015.

[4] 李春葆.算法設計與分析（第2版）[M].清華大學出版社，2018.

[5] 劉文強，周波等.算法分析與設計課程中0-1背包問題的探討[J].高師理科學刊，2018.6：82-85