動態規劃算法概述

??動態規劃（dynamic programming）¹是一種與分治方法很像的方法，都是通過組合子問題的解來求解原問題。不同之處在于，動態規劃用于子問題重疊的情況，比如我們學過的斐波那契數列。在斐波那契數列的求解問題中，我們經常要對一個公共子問題進行多次求解，而動態規劃算法，則對每個子問題只求解一次，將其解保存在一個表格中，從而避免了大量的冗余計算量。

??動態規劃算法常用于尋找最優解問題（optimization problem）。而其規劃大概可分為四步：

??1.刻畫一個最優解的結構特征。

??2.遞歸的定義最優解的值。

??3.計算最優解的值。

??4.利用計算出的信息構造一個最優解²。

??我們將以《算法導論》中的一個習例作為展示的對象，講解動態規劃算法的應用方法。

鋼條切割問題

現有某公司，購買長鋼條以切割成短鋼條出售。若不計切割成本，請求出如何切割以使公司利益最大。該公司短鋼條售價如下：

長度：1 2 3 4 5 6 7 8 9 10

價格：1 5?8 9 10 17 20 24 30

??

??現假設一段鋼條的長度為n，我們可以試求當 n = 4時，我們能獲得的最大收益。此時，我們對于第一次分割有5種選擇（0,1,2,3,4），以此類推，對于n = 4的情況，我們一共有8種情形：（4），（1,3），（2,2），（3,1），（1,1,2），（1,2,1），（2,1,1），（1,1,1,1）。易算得，最高價值為（2,2）情況下取得，最高收益為10.

??那么，我們如何用函數來描述這一過程呢？首先，我們可以假設第一次切割所得的第一部分鋼條長度為x （屬于[0,n]）。則我們現在有了兩根鋼條，一根長為x，另一根長為 n - x。那么長為n的鋼條所得利益的最優解就來自于長為x 和 n - x兩段鋼條最優解的和。如此劃分，即可將問題逐步化簡為一個個子問題，以R來表示公司所得利益，P來表示鋼條單價，則有R對n的函數： ????????????

R_n?= max（P_x?+ R_{（n - x)})。

??

普通遞歸方法實現

??可以看出上述公式是一個很明顯的遞歸函數，我們很容易就可以得到下列代碼：

?

1 #include<iostream> 2 #include<vector> 3 #include<algorithm> 4 #define?null?-1 5 using?namespace?std; 6 ? 7 int?cut_rod(int?n, vector<int> p) { 8 if?(n?== 0) ?return?0; 9 int?q = null; ?????????????????????????????????? 10 for?(int?i = 1; i <= n; i++) { 11 q = max(q , p[i-1]?+ cut_rod(n?- i, p) ); 12 } 13 return?q; 14 } 15 ? 16 int?main() { 17 cout <<?"輸入產品各段數所對應的價格（從小到大）"?<<?endl; 18 int?n = 0; 19 vector<int> p; 20 while?(cin >>?n ?&& n != null) { ???????????????????????????//輸入-1表示停止 21 p.push_back(n); 22 n = 0; 23 } 24 vector<int> results(p.size() + 1, null); ???????????????????//在result中創建n + 1個元素（[0,n]共n+1個），并統一賦值為null 25 cout <<?"請輸入所需切割鋼材長度"?<<?endl; 26 cin >>?n; 27 cout <<?cut_rod(n, p); 28 //cout << memo_cut_rod(n, p, results); 29 //cout << bot_cut_rod(n, p, results); 30 return?0; 31 }

?

我們已在斐波那契數列的學習中證明了，這種算法的缺點是很明顯的，隨著遞歸的深入，其計算量會爆炸性的增長。易得其時間復雜度 ： T = 2^N。

??那么我們要怎么利用動態規劃的方法來進行簡便運算呢？方法有兩種：一種稱之為帶備忘的自頂向下法（top-down with memoization³），另一種則是自底向上法（bottom-up method）。

帶備忘的自頂向下法

??此方法與正常的遞歸方法并無太大區別，但在過程中，每一個子問題的解都會被保存下來，在每次求解之前都會驗證是否已經對該子問題進行了求解，若是，則直接返回保存的值；不是，再進行正常運算。據此理論，易得代碼：

1 int?memo_cut_rod(int?n, vector<int> p, vector<int> results) { 2 if?(results[n]?> 0) return?results[n]; 3 if?(n?== 0) return?0; 4 int?q = null; 5 for?(int?i = 1; i <= n; i++) { 6 q = max(q, p[i - 1]?+ memo_cut_rod(n?- i, p,results)); 7 } 8 return?q; 9 } 10 ? 11 ? 12 int?main() { 13 cout <<?"輸入產品各段數所對應的價格（從小到大）"?<<?endl; 14 int?n = 0; 15 vector<int> p; 16 while?(cin >>?n ?&& n != null) { ???????????????????????????//輸入-1表示停止 17 p.push_back(n); 18 n = 0; 19 } 20 vector<int> results(p.size() + 1, null); ???????????????????//在result中創建n + 1個元素（[0,n]共n+1個），并統一賦值為null 21 cout <<?"請輸入所需切割鋼材長度"?<<?endl; 22 cin >>?n; 23 //cout << cut_rod(n, p); 24 cout <<?memo_cut_rod(n, p, results); 25 return?0; 26 }?

?

自底向上法

??自底向上法采用了與正常遞歸相似的順序，但免除了從頂到下的過程以及冗余的計算，直接從最小問題算起，最后構成最優解。其代碼如下：

int?bot_cut_rod(int?n,vector<int> p,vector<int> results) { results[0]?= 0; for?(int?j = 1; j <= n; ++j) { int?q = null; for?(int?i = 1; i <= j; ++i) { q = max(q, p[i -1]?+ results[j - i]); } results[j]?= q; } return?results[n]; }

?

總結

??自底向上法與帶備忘的自頂向下法具有相同的漸進運行時間，兩者的時間復雜度都為 T = n²。相比之前的2ⁿ強了太多。而使用動態規劃算法的重中之重，是找好問題劃分的方法，將問題一步一步化簡到最小，把大問題化簡成一個個小問題，小問題往往比大問題好解的多，最后再由小問題推導出大問題的答案，就算是大功告成了。 ???

?

?

?

?

?

?

注釋：

1.此處的programming是指一種表格法，而非編程

2.當我們僅僅需要一個最優解的值的時候，我們往往可以省略掉第4步。

3.此處并非拼寫錯誤，確實為memoization,而非memorization。前者源自memo，為備忘之意。

?

????????????參考文獻：

《算法導論》

轉載于:https://www.cnblogs.com/PabloZeal/p/6657961.html

總結

以上是生活随笔為你收集整理的《算法导论》中动态规划求解钢条切割问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。