運籌學(xué)中的經(jīng)典動態(tài)規(guī)劃

大家好，我是新來的小小編，小何同學(xué)。

//一個老年退休OI選手//

應(yīng)我們大大老板的要求，小小編今天打算給大家?guī)硪恍┰谶\籌學(xué)中比較基礎(chǔ)的動態(tài)規(guī)劃問題，也算在之前的小舟小編的基礎(chǔ)上加一些東西吧!

小舟小編之前在公眾號中已經(jīng)簡要地給大家介紹過了什么是動態(tài)規(guī)劃問題，同時他也對三個比較基礎(chǔ)的概念:階段，狀態(tài)，決策做了比較詳細的解釋，如果各位觀眾姥爺還沒有看的話，可以去了解一下。

接下來就是我們大大老板給我的任務(wù)了，這也是幾個比較典型的動態(tài)規(guī)劃的例子，我們一起來看一下吧!

No.1

Investment Problem

這問題大概就是說我們有十個投資機會，有八個投資項目，我們可以在每個投資項目.上投資多個投資機會以獲得相應(yīng)的回報，那我們怎么才能獲得最大的回報??

首先我們要知道動態(tài)規(guī)劃的精髓:無后效性，就是前面做的決策并不會影響后面做的決策，也就是說我們前面的i個投資項目中花了j個投資的機會得出來的最大利益，無論我們在后面的項目中花費多少的投資機會，都不會引起前面的改變。那么很顯然，我們可以推出第一-個的所有的投資方法，然后只要推出第二個，第三個，到最后一個，最后得出來解。

然后就是我們最為激動人心的coding time了!

上代碼

#include
#include
#include
using  namespace std;double value[9][5] = { {0,0,0,0,0},{0,4.1,5.8,6.5,6.8}, {0,1.8,3.0,3.9,4.5},{0,1.5,2.5,3.3,3.8},{0,2.2,3.8,4.8,5.5},{0,1.3,2.4,3.2,3.9},{0,4.2,5.9,6.6,6.8},{0,2.2,3.5,4.2,4.6},{0,1.0,1.7,2.3,2.8} };
double max(double x, double y){   if (x > y) return x;   return y;}int main(){       double dp[9][11];//前i個投資項目用j個投資數(shù)的最大價值   memset(dp, 0, sizeof(dp));   for (int i = 1; i <= 8; ++i)//項目   {       for (int j = 1; j <= 10; ++j)//到i時用了j個       {           for (int d = 0; d <= 4 && d <= j; ++d)//在i這里用了d個投資           {               for (int k = 0; k <= j - d; ++k)//前i-1個用了k個投資               {                   dp[i][j] = max(dp[i][j], dp[i - 1][k] + value[i][d] + 0.5 * (j - k - d));               }           }       }   }   cout << dp[8][10];   return 0;}

限于今天要講的題目可能有點多，所以說沒法給

大家很詳細的講解，下面的鏈 接中有我們大大老

板的PPT，里面很詳細的介紹了怎么得出結(jié)果，怎

么分析，如果有不懂的地方，請移步下面鏈接。

然后課件里面有幾道類似的題目，有興趣的觀眾

姥爺們也可以去動動手。

No.2

Shortest?Path?Problem

在動態(tài)規(guī)劃中，除了這種求最大值的算法之外,還有些是要求我們?nèi)デ笞钚≈档?，這個就要求我們必須在開始處理數(shù)據(jù)之前必須把所有的儲存空間先格式化一遍，不過這里的儲存空間并不是意味著把它們?nèi)扛袷交癁榱?，而是格式化?strong>無窮大，正因為我們要求的是最小值,所以說無窮大，相當于是不可能的。這跟我們求最大值時,把所有的初始化為零是一-個道理。

然后我們看一下例題。

這個題的意思就是說我們要從紐約去往洛杉磯，

中間可以途經(jīng)很多其他的的地點，每兩個節(jié)點之

間有一-個固定的路程長度，那么我們達到終點的

最短距離是多少呢?

我們先開始分析下，首先在我們制定數(shù)據(jù)的時候，我們把任意兩個地，點之間的所有的距離都設(shè)為無窮大，這就表示這兩個地點之間是不聯(lián)通的，然后再通入我們輸入的數(shù)據(jù)，把他們的距離再修改，如果他們的距離不是無窮大就說明他們之間是聯(lián)通的。用我們定義的矩陣dp來記錄兩點之間的最短距離，下面的i和j所表示的是起點和終點，然后我們要做的就是不停的用k，也就是起點和終點之間可能經(jīng)過的點來做松弛操作，把它們之間的最小距離，一步一步的刷新，最后得出子最優(yōu)解。

但是請各位觀眾老爺要注意，這種算法的前面的三重循環(huán)必須有嚴格的順序要求，因為如果我們一旦把循環(huán)的層次給改變，就可能導(dǎo)致當我們刷新-一個最優(yōu)解的時候,他的子最優(yōu)解并沒有得出來，從而導(dǎo)致我們現(xiàn)在所求的最優(yōu)解是錯誤的。所以請牢牢記住這一點。

下面就是我們的代碼了，小何子，上代碼 !

//Floyd算法,動態(tài)規(guī)劃的思想，另外沒有直接寫入數(shù)據(jù)，因為實在是太多了。。。。。。//includeusing namespace std;int dp[11][11];int min(int x, int y){   if (x > y) return y;   return x;}int main(){   int way_number;//路徑的數(shù)量   cin >> way_number;   for (int i = 0; i <= 10; ++i)        for (int j = 0; j <= 10; ++j)            dp[i][j] = 0x3fffffff;//無窮大的話等于不通    for (int i = 1; i <= way_number; ++i)    {        int a, b, v;        cin >> a >> b >> v;       dp[a][b] = v;   }   for (int i = 0; i <= 10; ++i)       dp[i][i] = 0;   for (int k = 1; k <= 10; ++k)       for (int i = 1; i <= 10; ++i)           for (int j = 1; j <= 10; ++j)           {               if (dp[i][j] < 0x3fffffff && dp[k][j] < 0x3fffffff)//防止爆int                   dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);           }   cout << dp[1][10];   return 0;

這種求最小值的問題，本質(zhì)上和那種求最大值的問題是相似的，但是我們要注意的是這種問題的初始化的方式是不同的，千萬，千萬，千萬不能忘記了初始化。還有就是一定要把它的最初狀態(tài)給修改下，-般就是在0的時候，還有的就是因為我們設(shè)置的是最大值，進行運算的時候，可能會爆掉儲存的空間，所以說我們在進行預(yù)算的時候，最好加一個特判，否則也有可能會出現(xiàn)bug。

大大老板的課件里面還有幾個跟這個比較相似的題目，各位看官老爺有興趣的也可以去看一下。那么今天的全部內(nèi)容到這里就結(jié)束了，小編也要期末復(fù)習(xí)了，可能也要隔段時間才給能大家送上新的推文吧。

另外，下面是小編代碼和大大老板ppt鏈接:

https://pan.baidu.com/s/11FLHF0wF60Ud58dNUCw4g?

提取碼：yn5i

復(fù)制這段內(nèi)容后打開百度網(wǎng)盤手機App，操作更方便哦