-
一、什么是動態規劃算法動態規劃算法是通過拆分問題，定義問題狀態和狀態之間的關系，使得問題能夠以遞推（或者說分治）的方式去解決。動態規劃算法的基本思想與分治法類似，也是將待求解的問題分解為若干個子問題（階段），按順序求解子階段，前一子問題的解，為后一子問題的求解提供了有用的信息。在求解任一子問題時，列出各種可能的局部解，通過決策保留那些有可能達到最優的局部解，丟棄其他局部解。依次解決各子問題，最后一個子問題就是初始問題的解。二、動態規劃算法的實現動態規劃的主要難點在于理論上的設計，也就是上面4個步驟的確定，一旦設計完成，實現部分就會非常簡單。使用動態規劃求解問題，最重要的就是確定動態規劃三要素：（1）問題的階段（2）每個階段的狀態（3）從前一個階段轉化到后一個階段之間的遞推關系。遞推關系必須是從次小的問題開始到較大的問題之間的轉化，從這個角度來說，動態規劃往往可以用遞歸程序來實現，不過因為遞推可以充分利用前面保存的子問題的解來減少重復計算，所以對于大規模問題來說，有遞歸不可比擬的優勢，這也是動態規劃算法的核心之處。確定了動態規劃的這三要素，整個求解過程就可以用一個最優決策表來描述，最優決策表是一個二維表，其中行表示決策的階段，列表示問題狀態，表格需要填寫的數據一般對應此問題的在某個階段某個狀態下的最優值（如最短路徑，最長公共子序列，最大價值等），填表的過程就是根據遞推關系，從1行1列開始，以行或者列優先的順序，依次填寫表格，最后根據整個表格的數據通過簡單的取舍或者運算求得問題的最優解。f（n，m）=max{f（n-1，m）， f（n-1，m-w［n］）+P（n，m）}三、動態規劃算法基本思想與策略編輯動態規劃算法的基本思想與分治法類似，也是將待求解的問題分解為若干個子問題（階段），按順序求解子階段，前一子問題的解，為后一子問題的求解提供了有用的信息。在求解任一子問題時，列出各種可能的局部解，通過決策保留那些有可能達到最優的局部解，丟棄其他局部解。依次解決各子問題，最后一個子問題就是初始問題的解。由于動態規劃解決的問題多數有重疊子問題這個特點，為減少重復計算，對每一個子問題只解一次，將其不同階段的不同狀態保存在一個二維數組中。四、動態規劃算法基本框架for（j=1; j《=m; j=j+1） // 第一個階段xn［j］ = 初始值;for（i=n-1; i》=1; i=i-1）// 其他n-1個階段for（j=1; j》=f（i）; j=j+1）//f（i）與i有關的表達式xi［j］=j=max（或min）{g（xi-1［j1:j2］）， 。。。。。。， g（xi-1［jk:jk+1］）};t = g（x1［j1:j2］）; // 由子問題的最優解求解整個問題的最優解的方案print（x1［j1］）;for（i=2; i《=n-1; i=i+1）{t = t-xi-1［ji］;for（j=1; j》=f（i）; j=j+1）if（t=xi［ji］）break;}五、電路布線問題的幾種動態規劃算法/*Name：Copyright：Author：巧若拙Date： 01-04-17 07:48DescripTIon： 電路布線【問題描述】在一塊電路板的上、下兩端分別有n個接線柱。根據電路設計，要求用導線（i，π（i））將上端接線柱i與下端接線柱π（i）相連。其中，π（i），1《=i《=n是{1，2，…，n}的一個排列。導線（i，π（i））稱為該電路板上的第i條連線。對于任何1《=i π（j）。在制作電路板時，要求將這n條連線分布到若干絕緣層上。在同一層上的連線不相交。你的任務是要確定將哪些連線安排在第一層上，使得該層上有盡可能多的連線。換句話說，就是確定導線集Nets={ i，π（i），1《=i《=n}的最大不相交子集。【輸入形式】輸入文件第一行為整數n；第二行為用一個空格隔開的n個整數，表示π（i）。【輸出形式】輸出文件第一行為最多的連線數m，第2行到第m+1行輸出這m條連線（i，π（i））。【輸入樣例】101 82 73 44 25 56 17 98 39 1010 6【輸出樣例】4算法1：int MNS（int i， int j）;//自頂向下的備忘錄算法設置一個備忘錄數組s［N+1］［N+1］，s［i］［j］表示從上接線柱1-i發出的導線連接到下接線柱1-j，能生成的不相交導線的最大條數。利用原問題的遞歸關系，使用遞歸函數來求解。狀態方程：當i=1時，s［1］［j］ = （j《c［1］） ？ 0 ： 1;當i》1時，若j《c［i］，則s［i］［j］ = s［i-1］［j］; 否則s［i］［j］ = max（s［i-1］［c［i］-1］+1， s［i-1］［j］）;算法2：int MNS_2（int n）;//自底向上的動態規劃算法從i=1開始，依次記錄每一個s［i］［j］，最后獲得最優解s［N］［N］。算法3：int MNS_3（int n）;//優化的動態規劃算法是對算法2的優化，算法2中用到的備忘錄數組s［N+1］［N+1］占空間較大，實際上下一行數據是利用上一行的數據生成的，與更早的數據沒有關系，于是可以用兩個一維數組pre［N+1］和cur［N+1］代替s［N+1］［N+1］。最后寫了一個函數void Traceback（int n）; //輸出滿足條件的導線該函數需要用到備忘錄數組s［N+1］［N+1］，故只能對算法1和算法2產生的結果有效。算法4：與算法2相似，但思路更清晰明了的一種算法。算法的邏輯，與最長公共子序列很相似。設a［i］［j］為上端接線柱i與下端接線柱j前的最大不相交子集，則：若i與j相連，則a［i］［j］ = a［i-1］［j-1］ + 1若i與j不相連，則a［i］［j］ = max（a［i］［j-1］， a［i-1］［j］）說明：算法2雖然代碼更復雜，但是它做了分類判斷，減少了很多不必要的計算，效率更高。算法5：對算法4的改進：分階段討論，避免不必要的計算。與算法2相類似，對下端的接線柱j進行了分段討論：分成j《c［i］， j==c［i］和j》c［i］三個區間，分別求a［i］［j］的值，效率更高。算法6：int MNS_4（int n）;//將問題轉化為求最長不下降序列注意到電線上端的接線柱已經按順序排列，問題可以轉化為求數組c［N+1］的最長不下降序列*/#include《iostream》#include《string》using namespace std;int MNS（int i， int j）;//自頂向下的備忘錄算法int MNS_2（int n）;//自底向上的動態規劃算法void Traceback_1（int n）; //輸出滿足條件的導線void Traceback_2（int n）; //輸出滿足條件的導線void Traceback_3（int n）; //輸出滿足條件的導線int MNS_3（int n）;//優化的動態規劃算法int MNS_4（int n）;//另一種思路的動態規劃算法int MNS_5（int n）;//對算法4的改進：分階段討論，避免不必要的計算int MNS_6（int n）;//將問題轉化為求最長不下降序列const int N = 10;int c［N+1］ = {0，8，7，4，2，5，1，9，3，10，6};int s［N+1］［N+1］;int a［N+1］［N+1］;int b［N+1］［N+1］;int pre［N+1］; //上一行記錄int cur［N+1］; //當前行記錄int S［N+1］; //記錄到元素i為止的最長上升子序列的長度int main（）{cout 《《 MNS（N， N） 《《 endl;cout 《《 MNS_2（N） 《《 endl;cout 《《 MNS_3（N） 《《 endl;cout 《《 MNS_4（N） 《《 endl;cout 《《 MNS_5（N） 《《 endl;cout 《《 MNS_6（N） 《《 endl;Traceback_1（N）;Traceback_2（N）;Traceback_3（N）;return 0;}int MNS（int i， int j）//自頂向下的備忘錄算法{if （s［i］［j］ 》 0）return s［i］［j］;if （i == 1） //處理第一根導線{s［i］［j］ = （j 《 c［i］） ？ 0 ： 1;}else{s［i］［j］ = MNS（i-1， j）;if （j 》= c［i］ && MNS（i-1， c［i］-1）+1 》 s［i］［j］）s［i］［j］ = s［i-1］［c［i］-1］ + 1; //s［i-1］［c［i］-1］在if語句中記錄過了}return s［i］［j］;}int MNS_2（int n）//自底向上的動態規劃算法{//先處理第一根導線for （int j=1; j《c［1］; j++）s［1］［j］ = 0;for （int j=c［1］; j《=n; j++）s［1］［j］ = 1;//然后處理中間的導線for （int i=2; i《n; i++）{for （int j=1; j《c［i］; j++）{s［i］［j］ = s［i-1］［j］;}for （int j=c［i］; j《=n; j++）{s［i］［j］ = （s［i-1］［c［i］-1］+1 》 s［i-1］［j］） ？ s［i-1］［c［i］-1］+1 ： s［i-1］［j］;}}//再處理最后一根導線s［n］［n］ = （s［n-1］［c［n］-1］+1 》 s［n-1］［n］） ？ s［n-1］［c［n］-1］+1 ： s［n-1］［n］;return s［n］［n］;}void Traceback_1（int n） //輸出滿足條件的導線{int j = n;for （int i=n; i》1; i--）{if （s［i］［j］ 》 s［i-1］［j］）{cout 《《 i 《《 “ - ” 《《 c［i］ 《《 endl;j = c［i］ - 1;}}if （j 》= c［1］）{cout 《《 1 《《 “ - ” 《《 c［1］ 《《 endl;}}void Traceback_2（int n） //輸出滿足條件的導線{int j = n;for （int i=n; i》1; i--）{if （a［i］［j］ 》 a［i-1］［j］）{cout 《《 i 《《 “ - ” 《《 c［i］ 《《 endl;j = c［i］ - 1;}}if （j 》= c［1］）{cout 《《 1 《《 “ - ” 《《 c［1］ 《《 endl;}}void Traceback_3（int n） //輸出滿足條件的導線{int j = n;for （int i=n; i》1; i--）{if （b［i］［j］ 》 b［i-1］［j］）{cout 《《 i 《《 “ - ” 《《 c［i］ 《《 endl;j = c［i］ - 1;}}if （j 》= c［1］）{cout 《《 1 《《 “ - ” 《《 c［1］ 《《 endl;}}int MNS_3（int n）//優化的動態規劃算法{//先處理第一根導線for （int j=1; j《c［1］; j++）pre［j］ = 0;for （int j=c［1］; j《=n; j++）pre［j］ = 1;//然后處理中間的導線for （int i=2; i《n; i++）{ //處理當前行curfor （int j=1; j《c［i］; j++）{cur［j］ = pre［j］;}for （int j=c［i］; j《=n; j++）{cur［j］ = （pre［c［i］-1］+1 》 pre［j］） ？ pre［c［i］-1］+1 ： pre［j］;}//復制當前行信息cur到prefor （int j=1; j《=n; j++）{pre［j］ = cur［j］;}}//再處理最后一根導線cur［n］ = （pre［n-1］+1 》 pre［n］） ？ pre［n-1］+1 ： pre［n］;return cur［n］;}int MNS_4（int n）//另一種思路的動態規劃算法，與最長公共子序列很相似{for （int i=1; i《=n; i++）{for （int j=1; j《=n; j++）{if （j == c［i］）a［i］［j］ = a［i-1］［j-1］ + 1;elsea［i］［j］ = max（a［i-1］［j］， a［i］［j-1］）;}}return a［n］［n］;}int MNS_5（int n）//對算法4的改進：分階段討論，避免不必要的計算{for （int i=1; i《=n; i++）{for （int j=1; j《c［i］; j++）//在接線柱c［i］的左側區域，最優解與不包含接線柱i的一致{b［i］［j］ = b［i-1］［j］;}b［i］［c［i］］ = b［i-1］［c［i］-1］ + 1;for （int j=c［i］+1; j《=n; j++）//在接線柱c［i］的右側區域，最優解可能包含接線柱i，也可能不包含i{b［i］［j］ = max（b［i-1］［j］， b［i］［j-1］）;}}return a［n］［n］;}int MNS_6（int n）//將問題轉化為求最長不下降序列{S［1］ = 1; //默認到元素i為止的最長上升子序列的長度為1for （int i=2; i《=n; i++）{int m = 0;for （int j=i-1; j》0; j--）//逆序查找不大于A［i］，且最長的元素{if （c［i］ 》 c［j］ && S［j］ 》 m）{m = S［j］;}}S［i］ = m + 1;}int len = S［n］;for （int i=n-1; i》0; i--）{if （S［i］ 》 len）{len = S［i］;}}return len;}
