重慶達內IT培訓
美國上市IT培訓機構

15023458194

重慶java培訓班:關于動態規劃法

  • 時間:2021-04-07 13:38
  • 發布:重慶達內
  • 來源:重慶達內

概念

動態規劃法離不開一個關鍵詞,拆分 ,就是把求解的問題分解成若干個子階段,前一問題的結果就是求解后一問題的子結構。在求解任一子問題時,列出各種可能的局部解,通過決策保留那些有可能達到最優的局部解,丟棄其他局部解。依次解決各子問題,最后一個子問題就是初始問題的解。

適用性

適用動態規劃的問題必須滿足最優化原理和無后效性。

最優化原理可這樣闡述:一個最優化策略具有這樣的性質,不論過去狀態和決策如何,對前面的決策所形成的狀態而言,余下的諸決策必須構成最優策略。簡而言之,一個最優化策略的子策略總是最優的。一個問題滿足最優化原理又稱其具有最優子結構性質。

將各階段按照一定的次序排列好之后,對于某個給定的階段狀態,它以前各階段的狀態無法直接影響它未來的決策,而只能通過當前的這個狀態。換句話說,每個狀態都是過去歷史的一個完整總結。這就是無后向性,又稱為無后效性。

解題思路

1.確定最優子結構:比如我們要求的結果F(X)的最優子結構可能為F(X-1)和F(X-2)

2.列轉移方程:根據最優子結構可以列出轉移方程F(X)=F(X-1)+F(X-2)

3.確定邊界值:確定問題的邊界,即當F(n)有可以確定的具體的值

以上概述是純粹是為了顯得官方一點,下面我們開始說人話

開始說人話

動態規劃法,規劃的意思就是劃分,求解一個問題時,把問題劃分成多個子階段,比如兔子繁殖問題,

有一對兔子,從出生后第3個月起每個月都生一對兔子,小兔子長到第三個月后每個月又生一對兔子,假如兔子都不死,問第n個月的兔子總數為多少?

對于這個問題,我們可以根據月份把問題劃分為n個階段,每個月的兔子數,都會等于前一個月的兔子數加上這個月新出生的兔子數,

所以 第n個月的兔子數=第n-1個月的兔子數+新出生的兔子數,

而 新出生的兔子數=有繁殖能力的兔子數=兩個月前的兔子數,

即:第n個月的兔子數=第n-1個月的兔子數+第n-2個月的兔子數

所以我們可以知道,我們要求的問題F(n)的最優子結構就是F(n-1)和F(n-2) ------對應解題思路的確定最優子結構

接著我們可以列出求解的方程 F(n)=F(n-1)+F(n-2) ----------列轉移方程

對于方程F(n) = F(n-1)+F(n-2) 我們發現 F(n-1)和F(n-2)的結果也不知道,但是我們可以用同樣的計算方法去求,F(n-1)=F(n-2)+F(n-3)以此類推,但是F(n)的在當n等于多少的時候才有確定的值呢,F(1)=1,F(2) = 1,這兩個就是F(n)的邊界值; -------確定邊界值

然后我們很容易就能寫出代碼

int f(int n){

if(n==1||n==2){

return 1;

}

return f(n-1)+f(n-2);

}

這就是使用動態規劃法解題的基本思路

確定最優子結構——》列轉移方程——》確定邊界值

上樓梯問題

一個樓梯有 10 級臺階,從下往上走,每跨一步只能向上邁 1 級或者 2 級臺階,請問一共有多少種走法?

解題思路:

要想走到第 10 級臺階,要么是先走到第 9 級,然后再邁一步 1 級臺階上去,要么是先走到第 8 級,然后一次邁 2 級臺階上去。

這樣的話,走到 10 級臺階的走法數,就等于走到 9 級臺階的走法數,加上走到 8 級臺階的走法數。

F(10) = F(9) + F(8) -------確定最優子結構

而且不光是 10 級臺階如此,走到任何一級臺階的走法數,都符合這個邏輯,因此就可以得出一個通用公式:

F(x) = F(x-1) + F(x-2) -------列轉移方程

其中上一級臺階的方式只有一種,而上兩級臺階的方式有兩種,得到F(1)=1,F(2)=2 -----找邊界值

代碼如下:

int F1(int n){

if(n==1){

return 1;

}

if(n==2){

return 2;

}

return F1(n-1)+F1(n-2);

}

但是很容易發現,這個代碼的時間復雜度是O(2^n),當n的值較大的時候,計算的需要很長的時間

我們可以對代碼進行簡單的處理

int F2(int n){

if(n==1){

return 1;

}

if(n==2){

return 2;

}

int t1 = 1;

int t2 = 2;

int temp = 0;

for(int i=3;i<=n;i++){

temp = t1+t2;

t1 = t2;

t2 = temp;

}

return temp;

}

這樣時間復雜度就降低了很多

兔子問題

同理,兔子繁殖問題,我們也可以對代碼進行同樣的處理

void F(int n){

int[] i = new int[n];//兔子數

int[] s;//有生育能力的兔子數

i[0] = 1;

int t = 0;

for(int j = 0;j

if(j>=2){

t = i[j - 2];

}

if(j>=1){

i[j]=i[j-1]+t;

}

System.out.println("第"+(j+1)+"個月份的兔子數:"+i[j]);

}

}

01背包問題

01背包問題是動態規劃法的經典問題

有一個背包,可以裝載重量為5kg的物品。

有4個物品,他們的重量和價值如下。

背包:載重5kg

物品1

重量: 1kg

價值:¥3

物品2

重量:2kg

價值:¥4

物品3:

重量: 3kg

價值:¥5

物品4

重量:4kg

價值:¥6

那么請問,在不得超過背包的承重的情況下,將哪些物品放入背包,可以使得總價值最大?

總重量是5kg,從四個物品中選,我們要求的問題就是:F(5,4),

對于第四個物品就只有兩種情況,我們可以選擇選,或者是不選

不選的話就還是5kg,只從前面三個物品去選,F(5,3)

選的話就是還剩下1kg,從前面三個去選,F(1,3)

F(5,4) = max { F(1,3) + 6, F(5,3) }

所以我們列出轉移方程:

F(W,N) =max { F(W-Wn, N-1) + Vn,F(W, N-1) } (w是重量,n是從前n個去選,Wn是第n個的重量,Vn是第n個的價值)

接下來就是找臨界值了:

當重量只剩下0kg的時候,就沒有能夠選擇的物品了,最大價值就是0,所以F(0,n)=0,

當只是剩下的重量大于0,但是已經遍歷到從前1個物品中選擇時,那么能選擇的物品就只有第一個,最大價值就是3,即F(n,1)=3

具體代碼如下:

static int F(int weight,int i,res[] resarr){//weight是重量,resarr保存的是物品重量和價值

if(weight==0){

return 0;

}

if(i==1){

return 3;

}

if(weight

return F(weight,i-1,resarr);

}

return Math.max(F(weight-resarr[i].getWeight(),i-1,resarr)+resarr[i].getValue(),F(weight,i-1,resarr));

}

上一篇:重慶java培訓機構:二分查找
下一篇:重慶java培訓:面向對象編程

重慶Java培訓課程大綱之培優班

重慶Java大數據培訓課程大綱

重慶java培訓:面向對象編程

重慶java培訓班:關于動態規劃法

  • 關注微信公眾號

    回復關鍵字:視頻資料

    免費領取 達內課程視頻學習資料

  • 視頻學習QQ群

    添加QQ群:1143617948

    免費領取達內課程視頻學習資料

Copyright ? 2018 Tedu.cn All Rights Reserved 京ICP備08000853號-56 京公網安備 11010802029508號 達內時代科技集團有限公司 版權所有

選擇城市和中心
江西省

貴州省

廣西省

海南省

免费V片无码动漫在线观看网址-男人的天堂无码动漫av