五大经常使用算法 之 动态规划法
一、基本概念
??? 動態規劃過程是：每次決策依賴于當前狀態。又隨即引起狀態的轉移。
一個決策序列就是在變化的狀態中產生出來的，所以，這樣的多階段最優化決策解決這個問題的過程就稱為動態規劃。
??? 動態規劃是運籌學中用于求解決策過程中的最優化數學方法。
當然。我們在這里關注的是作為一種算法設計技術，作為一種使用多階段決策過程最優的通用方法。
它是應用數學中用于解決某類最優化問題的重要工具。
??? 假設問題是由交疊的子問題所構成，我們就能夠用動態規劃技術來解決它。一般來說，這種子問題出如今對給定問題求解的遞推關系中，這個遞推關系包括了同樣問題的更小子問題的解。動態規劃法建議，與其對交疊子問題一次重新的求解，不如把每一個較小子問題僅僅求解一次并把結果記錄在表中（動態規劃也是空間換時間的）。這樣就能夠從表中得到原始問題的解。
??? 動態規劃經常常使用于解決最優化問題，這些問題多表現為多階段決策。
??? 關于多階段決策：
??? 在實際中，人們經常遇到這樣一類決策問題：即因為過程的特殊性，能夠將決策的全過程根據時間或空間劃分若干個聯系的階段。
而在各階段中。人們都須要作出方案的選擇。我們稱之為決策。而且當一個階段的決策之后，經常影響到下一個階段的決策，從而影響整個過程的活動。這樣，各個階段所確定的決策就構成一個決策序列，常稱之為策略。
因為各個階段可供選擇的決策往往不止一個。因而就可能有很多決策以供選擇，這些?可供選擇的策略構成一個集合，我們稱之為同意策略集合（簡稱策略集合）。每一個策略都對應地確定一種活動的效果。我們假定這個效果能夠用數量來衡量。
因為不同的策略經常導致不同的效果，因此，怎樣在同意策略集合中選擇一個策略，使其在預定的標準下達到最好的效果。經常是人們所關心的問題。我們稱這種策略為最優策略，這類問題就稱為多階段決策問題。
??? 多階段決策問題舉例：機器負荷分配問題
??? 某種機器能夠在高低兩種不同的負荷下進行生產。在高負荷下生產時。產品的年產量g和投入生產的機器數量x的關系為g=g(x)，這時的年完善率為a，即假設年初完善機器數為x，到年終時完善的機器數為a*x(0<a<1)；在低負荷下生產時，產品的年產量h和投入生產的機器數量y的關系為h=h(y)。對應的完善率為b(0<b<0)。且a<b。
??? 假定開始生產時完善的機器熟練度為s1。
要制定一個五年計劃，確定每年投入高、低兩種負荷生產的完善機器數量，使5年內產品的總產量達到最大。
??? 這是一個多階段決策問題。
顯然能夠將全過程劃分為5個階段（一年一個階段），每一個階段開始時要確定投入高、低兩種負荷下生產的完善機器數，并且上一個階段的決策必定影響到下一個階段的生產狀態。決策的目標是使產品的總產量達到最大。這個問題常常使用數學方法建模，結合線性規劃等知識來進行解決。
二、基本思想與策略
??? 基本思想與分治法類似，也是將待求解的問題分解為若干個子問題（階段），按順序求解子階段，前一子問題的解，為后一子問題的求解提供了實用的信息。
在求解任一子問題時，列出各種可能的局部解，通過決策保留那些有可能達到最優的局部解，丟棄其它局部解。依次解決各子問題，最后一個子問題就是初始問題的解。
??? 因為動態規劃解決的問題多數有重疊子問題這個特點。為降低反復計算。對每個子問題僅僅解一次，將其不同階段的不同狀態保存在一個二維數組中。
??? 與分治法最大的區別是：適合于用動態規劃法求解的問題，經分解后得到的子問題往往不是互相獨立的（即下一個子階段的求解是建立在上一個子階段的解的基礎上，進行進一步的求解）。
三、適用的情況
能採用動態規劃求解的問題的一般要具有3個性質：
（1）、最優化原理：假設問題的最優解所包括的子問題的解也是最優的，就稱該問題具有最優子結構，即滿足最優化原理。
（2）、無后效性：即某階段狀態一旦確定。就不受這個狀態以后決策的影響。也就是說，某狀態以后的過程不會影響曾經的狀態。僅僅與當前狀態有關；
（3）、有重疊子問題：即子問題之間是不獨立的，一個子問題在下一階段決策中可能被多次使用到（該性質并非動態規劃適用的必要條件，可是假設沒有這條性質。動態規劃算法同其它算法相比就不具備優勢）。
四、求解的基本步驟
動態規劃所處理的問題是一個多階段決策問題。一般由初始狀態開始。通過對中間階段決策的選擇，達到結束狀態。這些決策形成了一個決策序列。同一時候確定了完畢整個過程的一條活動路線(一般是求最優的活動路線)。動態規劃的設計都有著一定的模式。一般要經歷下面幾個步驟。
初始狀態→│決策1│→│決策2│→…→│決策n│→結束狀態
（1）劃分階段：依照問題的時間或空間特征。把問題分為若干個階段。在劃分階段時。注意劃分后的階段一定要是有序的或者是可排序的。否則問題就無法求解。
（2）確定狀態和狀態變量：將問題發展到各個階段時所處于的各種客觀情況用不同的狀態表示出來。
當然，狀態的選擇要滿足無后效性。
（3）確定決策并寫出狀態轉移方程：由于決策和狀態轉移有著天然的聯系，狀態轉移就是依據上一階段的狀態和決策來導出本階段的狀態。所以假設確定了決策。狀態轉移方程也就可寫出。但其實經常是反過來做。依據相鄰兩個階段的狀態之間的關系來確定決策方法和狀態轉移方程。
（4）尋找邊界條件：給出的狀態轉移方程是一個遞推式。須要一個遞推的終止條件或邊界條件。
一般，僅僅要解決這個問題的階段、狀態和狀態轉移決策確定了。就能夠寫出狀態轉移方程（包含邊界條件）。
實際應用中能夠按下面幾個簡化的步驟進行設計：
（1）分析最優解的性質。并刻畫其結構特征。
（2）遞歸的定義最優解。
（3）以自底向上或自頂向下的記憶化方式（備忘錄法）計算出最優值。
（4）依據計算最優值時得到的信息，構造問題的最優解。
五、算法實現的說明
??? 動態規劃的主要難點在于理論上的設計，也就是上面4個步驟的確定，一旦設計完畢。實現部分就會很easy。
??? 使用動態規劃求解問題，最重要的就是確定動態規劃三要素：問題的階段、每一個階段的狀態、從前一個階段轉化到后一個階段之間的遞推關系。
??? 遞推關系必須是從次小的問題開始到較大的問題之間的轉化，從這個角度來說，動態規劃往往能夠用遞歸程序來實現，只是由于遞推能夠充分利用前面保存的子問題的解來降低反復計算，所以對于大規模問題來說。有遞歸不可比擬的優勢。這也是動態規劃算法的核心之處。
??? 確定了動態規劃的這三要素，整個求解過程就能夠用一個最優決策表來描寫敘述，最優決策表是一個二維表，當中行表示決策的階段，列表示問題狀態。表格須要填寫的數據一般相應此問題的在某個階段某個狀態下的最優值（如最短路徑。最長公共子序列，最大價值等），填表的過程就是依據遞推關系，從1行1列開始，以行或者列優先的順序，依次填寫表格。最后依據整個表格的數據通過簡單的取舍或者運算求得問題的最優解。
六、動態規劃——幾個典型案例
1、計算二項式系數
問題描寫敘述：
??? 計算二項式系數
問題解析：
??? 在排列組合中，我們有下面公式：
??? 當n>k>0時。C(n,k)?=?C(n-1,k-1)?+?C(n-1,k)
??? 這個式子將C(n,k)的計算問題簡化為（問題描寫敘述）C(n-1,k-1)和C(n-1,k)兩個較小的交疊子問題。
??? 初始條件：C(n,n)?=?C(n,0)?=?0；
??? 我們能夠用填矩陣的方式求解C(n,k)：
?
??? 上圖即為二項式系數矩陣表。
??? 那么。我們要計算出任一C(n,k)。我們能夠嘗試求出全部的二項式系數表格。然后通過查表來進行計算操作。
??? 這里，我們的構建二項式系數表的函數為（填矩陣）：
??? int?BinoCoef(int?n,?int?k);
函數及詳細程序實現例如以下：
#include <stdio.h> #define MAX 100 int BinoCoef(int n, int k); int main(){int n,k,result;printf("Please input n and k:\n");scanf("%d %d",&n,&k);result = BinoCoef(n,k);printf("The corrsponding coefficent is %d !\n",result);return 0; } int BinoCoef(int n, int k){int data[MAX][MAX];int i,j;for(i=0;i<=n;i++){for(j=0;j<=((i<k)?i:k);j++) { if(i == 0||i == j) data[i][j] = 1; else data[i][j] = data[i-1][j] + data[i-1][j-1]; } } return data[n][k]; }
這里，我們要注意動態規劃時的這樣幾個關鍵點：
(1)、怎么描寫敘述問題。要把問題描寫敘述為交疊的子問題；
(2)、交疊子問題的初始條件（邊界條件）；
(3)、動態規劃在形式上往往表現為填矩陣的形式；
(4)、遞推式的依賴形式決定了填矩陣的順序。
2、三角數塔問題：
問題描寫敘述：
??? 設有一個三角形的數塔。頂點為根結點。每一個結點有一個整數值。從頂點出發，能夠向左走或向右走，要求從根結點開始，請找出一條路徑，使路徑之和最大。僅僅要輸出路徑的和。如圖所看到的：
?
??? 當然，正確路徑為13-8-26-15-24（和為86）。
問題解析：
??? 如今，怎樣求出該路徑？
??? 首先，我們用數組保存三角形數塔，并設置距離矩陣d[i][j]，用于保存節點(i,j)到最底層的最長距離，從而，d[1][1]即為根節點到最底層的最大路徑的距離。
| 行/列 | 1 | 2 | 3 | 4 | 5 |
| 1 | 13 | ? | ? | ? | ? |
| 2 | 11 | 8 | ? | ? | ? |
| 3 | 12 | 7 | 26 | ? | ? |
| 4 | 6 | 14 | 15 | 8 | ? |
| 5 | 12 | 7 | 13 | 24 | 11 |
方法一：遞推方式
??? 相應函數：void?fnRecursive(int,int);
??? 對于遞推方式。其基本思想是基于指定位置。逐層求解：
??? 舉例：找尋從點(1,1)開始逐層向下的路徑的最長距離。
??? 思想：自底向上的逐步求解（原因在于，這是一個三角形的矩陣形式，向上收縮，便于求解）。
??? 首先。在最底層，d[n][j]=a[n][j](將最底層的節點到最底層的最長路徑距離設置為節點值)。
??? 然后。逐層向上進行路徑距離處理，這里須要注意距離處理公式：
??? d[i-1][j]?=?min{?(d[i][j]?+?a[i-1][j]),?(d[i][j+1]?+?a[i-1][j])?}
??? 最后，遞推處理路徑距離至根節點就可以，這樣就建立了一個完整的路徑最長距離矩陣，用來保存三角數塔節點到最底層的最長路徑距離。
方法二：記憶化搜索方式
??? 相應函數：int?fnMemorySearch(int?i,int?j);
??? 記憶化搜索方式的核心在于保存前面已經求出的距離值，然后依據這些距離值能夠求出后面所需求解的距離值。
該函數的返回值即為節點(i,j)到最底層的最長路徑距離值。
??? 這里，我們能夠去考究這樣幾個問題：
（1）在什么時候結束？
（2）有何限制條件和一般情況處理？
??? 問題1解析：
??? 當d[i][j]>0時，則說明節點(i,j)到最底層的最長路徑距離已經存在，因此直接返回該值就可以。
??? 問題2解析：
??? 限制條件：當節點(i,j)位于最底層時，即i==n時，這時d[i][j]應該初始化為a[i][j]；
??? 一般情況處理：即節點(i,j)的賦值問題。
??? 這里有兩種情況：
??? 第一種情況，節點(i,j)相應的最長路徑的下一層節點為左邊節點：
??? 此時，d[i][j]?=?a[i][j]?+?fnMemorySearch(i+1,j);
??? 另外一種情況，節點(i,j)相應的最長路徑的下一層節點為右邊節點：
??? 此時，d[i][j]?=?a[i][j]?+?fnMemorySearch(i+1,j+1);
代碼實現：
#include <stdio.h> #include <stdlib.h> #define MAXN 101int n,d[MAXN][MAXN]; int a[MAXN][MAXN]; void fnRecursive(int,int); //遞推方法函數聲明 int fnMemorySearch(int,int); //記憶化搜索函數聲明 int main() {int i,j;printf("輸入三角形的行數n(n=1-100):\n");scanf("%d",&n);printf("按行輸入數字三角形上的數(1-100):\n");for(i=1; i<=n; i++)for(j=1; j<=i; j++)scanf("%d",&a[i][j]);for(i=1; i<=n; i++)for(j=1; j<=i; j++)d[i][j]=-1;//初始化指標數組printf("遞推方法：1\n記憶化搜索方法：2\n");int select;scanf("%d",&select);if(select==1){fnRecursive(i,j);//調用遞推方法printf("\n%d\n",d[1][1]);}else if(select==2){printf("\n%d\n",fnMemorySearch(1,1));//調用記憶化搜索方法}elseprintf("輸入錯誤！");return 0; } void fnRecursive(int i,int j) //遞推方法實現過程 {for(j=1; j<=n; j++)d[n][j]=a[n][j];for(i=n-1; i>=1; i--)for(j=1; j<=i; j++)d[i][j]=a[i][j]+(d[i+1][j]>d[i+1][j+1]?d[i+1][j]:d[i+1][j+1]); } int fnMemorySearch(int i,int j) //記憶化搜索實現過程 {if(d[i][j]>=0) return d[i][j];if(i==n) return(d[i][j]=a[i][j]);if(fnMemorySearch(i+1,j)>fnMemorySearch(i+1,j+1))return(d[i][j]=(a[i][j]+fnMemorySearch(i+1,j)));elsereturn(d[i][j]=(a[i][j]+fnMemorySearch(i+1,j+1))); }3、硬幣問題
問題描寫敘述：
??? 有n種硬幣，面值分別為V1,V2,…,Vn元，每種有無限多。
給定非負整數S。能夠選用多少硬幣，使得面值之和恰好為S元，輸出硬幣數目的最小值和最大值。（1<=n<=100,0<=S<=10000,1<=Vi<=S）
問題解析：
??? 首先證明該問題問題具有最優子結構。如果組合成S元錢有最優解。并且最優解中使用了面值Vi的硬幣。同一時候最優解使用了k個硬幣。那么，這個最優解包括了對于組合成S-Vi元錢的最優解。
顯然，S-Vi元錢的硬幣中使用了k-1個硬幣。如果S-Vi元錢另一個解使用了比k-1少的硬幣。那么使用這個解能夠為找S元錢產生小于k個硬幣的解。
與如果矛盾。
??? 另外。對于有些情況下，貪心算法可能無法產生最優解。
比方硬幣面值分別為1、10、25。
組成30元錢。最優解是3*10，而貪心的情況下產生的解是1*5+25。
??? 對于貪心算法，有一個結論：如果可換的硬幣單位是c的冪。也就是c^0、c^1、...、?c^k，當中整數c>1，k>=1。在這樣的情況下貪心算法能夠產生最優解。
上面已經證明該問題具有最優子結構，因此能夠用動態規劃求解該硬幣問題。
====>>>：
設min[j]為組合成j元錢所需的最少的硬幣數。max[j]為組合成j元錢所需的最多的硬幣數。
??? 從而有，對于最小組合過程。我們盡可能使用大面值的硬幣（不是必定，否則成為貪心算法）。其滿足以下的遞推公式：
當j=0時，min[0]?=?0。//即組合成0元錢的所需硬幣數為0。顯而易見。
當j>0時，假設j?>?Vk且min[j]?<?1?+?min[j-Vk]。則有min[j]?=?1?+?min[j-Vk]。對于這一步。其思想是盡可能通過大面值硬幣來降低所需硬幣數。
??? 而對于最大組合過程。我們則是盡量使用小面值的硬幣（此過程。同貪心算法一樣）。其滿足以下的遞推公式：
當j?=?0時，max[0]?=?0。//顯而易見。
當j?>?0時。假設j?>?Vk且max[j]?>?1?+?max[j?-?Vk]，則有max[j]?=?1?+?max[j-Vk]；
如此，我們對整個面值構成過程進行了簡單的處理，得到了不同面值和情況下所需的硬幣數。
??? 如今，舉例來說明此過程：
??? 就上面所提及的用1、10、25面值硬幣來組成30元錢的過程，我們進行相關說明：
??? 首先，min[0]?=?max[0]?=?0。同一時候初始化min[i]?=?INF，max[i]?=?-INF，i!=0。
??? 然后。我們依據上面的兩個遞推公式。能夠得到min[]和max[]的終于數據。
??? 其數據終于為：
??? min[]?=?{0,1,2,3,4,5,6,7,8,9,1,2,3,4,5,6,7,8,9,2,3,4,5,6,1,2,3,4,5,3};
??? max[]?=?{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,...,28,19,30};
??? 于是依據min[]和max[]，我們便能夠得到所需硬幣數。并通過print_ans函數打印詳細組合。
代碼實現：
#include <stdio.h> #include <stdlib.h>#define INF 100000000 #define MAXNUM 10000 #define MONEYKIND 100int n,S; int V[MONEYKIND]; int min[MAXNUM],max[MAXNUM];void dp(int*,int*); //遞推方法函數聲明 void print_ans(int*,int); //輸出函數聲明int main() {int i;printf("輸入硬幣的種數n(1-100):\n");scanf("%d",&n);printf("輸入要組合的錢數S(0-10000):\n");scanf("%d",&S);printf("輸入硬幣種類：\n");for(i=1; i<=n; i++){scanf("%d",&V[i]);}dp(min,max);printf("最小組合方案：\n");print_ans(min,S);printf("\n");printf("最大組合方案：\n");print_ans(max,S);return 0; }void dp(int *min,int *max) //遞推過程實現 {int i,j;min[0] = max[0] = 0;for(i=1; i<=S; i++)//初始化數組{min[i]=INF;max[i]=-INF;}for(i=1; i<=S; i++)for(j=1; j<=n; j++)if(i>=V[j]){if(min[i-V[j]]+1<min[i]){min[i]=min[i-V[j]]+1;//最小組合過程//printf("%d\n",min[i]);}if(max[i-V[j]]+1>max[i])max[i]=max[i-V[j]]+1;//最大組合過程} }void print_ans(int *d,int S) //輸出函數實現 {int i;for(i=1; i<=n; i++)if(S>=V[i]&&d[S]==d[S-V[i]]+1){printf("%d ",V[i]);print_ans(d,S-V[i]);break;} }??? 對于上面的代碼，還須要說明的是print_ans函數的實現過程：
??? 遞歸地打印出組合中的硬幣（面值由小到大），每次遞歸時降低已打印出的硬幣面值。
討論：
貪心算法的適用性（僅指最小組合）：
??? 對于貪心算法，有一個結論：如果可換的硬幣單位是c的冪。也就是c^0、c^1、...、?c^k，當中整數c>1，k>=1。在這樣的情況下貪心算法能夠產生最優解。
??? 貪心算法的過程：對硬幣面值進行升序排序。先取最大面值（排序序列最后一個元素）進行極大匹配（除法），然后對余數進行類上操作。
因此，在這里。注意貪心算法與動態規劃的差別：
??? 動態規劃和貪心算法都是一種遞推算法；
??? 均由局部最優解來推導全局最優解。
??? 不同點：
貪心算法：
??? (1)、貪心算法中。作出的每步貪心決策都無法改變，由于貪心策略是由上一步的最優解推導下一步的最優解，而上一部之前的最優解則不作保留。
??? (2)、由（1）中的介紹，能夠知道貪心法正確的條件是：每一步的最優解一定包括上一步的最優解
動態規劃算法：
??? (1)、全局最優解中一定包括某個局部最優解，但不一定包括前一個局部最優解，因此須要記錄之前的全部最優解；
??? (2)、動態規劃的關鍵是狀態轉移方程。即怎樣由以求出的局部最優解來推導全局最優解。
??? (3)、邊界條件：即最簡單的，能夠直接得出的局部最優解。
轉載于:https://www.cnblogs.com/brucemengbm/p/6875340.html
總結
以上是生活随笔為你收集整理的五大经常使用算法 之 动态规划法的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 1.8 小飞的电梯调度算法
- 下一篇： thymeleaf常用属性