日韩无码专区无码一级三级片|91人人爱网站中日韩无码电影|厨房大战丰满熟妇|AV高清无码在线免费观看|另类AV日韩少妇熟女|中文日本大黄一级黄色片|色情在线视频免费|亚洲成人特黄a片|黄片wwwav色图欧美|欧亚乱色一区二区三区

RELATEED CONSULTING
相關(guān)咨詢(xún)
選擇下列產(chǎn)品馬上在線(xiàn)溝通
服務(wù)時(shí)間：8:30-17:00
你可能遇到了下面的問(wèn)題
關(guān)閉右側(cè)工具欄

新聞中心

這里有您想知道的互聯(lián)網(wǎng)營(yíng)銷(xiāo)解決方案
從斐波那契數(shù)列和零一背包問(wèn)題探究動(dòng)態(tài)規(guī)劃

 本人看了vivo，阿里巴巴的校招算法題，可以明確知道絕對(duì)有動(dòng)態(tài)規(guī)劃。如果沒(méi)有，那么出題的面試官真的沒(méi)有水平。跌了N次的動(dòng)態(tài)規(guī)劃，Runsen最近也拼命搞動(dòng)態(tài)規(guī)劃。這篇文章浪費(fèi)了三天時(shí)間。

創(chuàng)新互聯(lián)建站是專(zhuān)業(yè)的潁州網(wǎng)站建設(shè)公司，潁州接單;提供做網(wǎng)站、成都網(wǎng)站設(shè)計(jì),網(wǎng)頁(yè)設(shè)計(jì),網(wǎng)站設(shè)計(jì),建網(wǎng)站,PHP網(wǎng)站建設(shè)等專(zhuān)業(yè)做網(wǎng)站服務(wù);采用PHP框架,可快速的進(jìn)行潁州網(wǎng)站開(kāi)發(fā)網(wǎng)頁(yè)制作和功能擴(kuò)展;專(zhuān)業(yè)做搜索引擎喜愛(ài)的網(wǎng)站,專(zhuān)業(yè)的做網(wǎng)站團(tuán)隊(duì),希望更多企業(yè)前來(lái)合作!

看了Leetcode公眾號(hào)的文章：https://mp.weixin.qq.com/s/rhyUb7d8IL8UW1IosoE34g

極客時(shí)間超哥的動(dòng)態(tài)規(guī)劃、拉勾教育的算法專(zhuān)欄。Runsen真的不想在動(dòng)態(tài)規(guī)劃，死一次又一次。死了N次，學(xué)了N次，就是他媽的寫(xiě)不出來(lái)。

動(dòng)態(tài)規(guī)劃需要搞定三個(gè)系列：三個(gè)背包，零錢(qián)問(wèn)題和股票問(wèn)題。今天，Runsen就開(kāi)始干掉最重要的「背包問(wèn)題」。

三個(gè)背包問(wèn)題：01背包，多重背包，完全背包。

動(dòng)態(tài)規(guī)劃前置知識(shí)

動(dòng)態(tài)規(guī)劃的名詞

「狀態(tài)轉(zhuǎn)移方程」：比如Runsen們一般看到的狀態(tài)轉(zhuǎn)移方程：dp[n] = dp[n-1] + dp[n-2]。

「最優(yōu)子結(jié)構(gòu)：一般由最優(yōu)子結(jié)構(gòu)，推導(dǎo)出一個(gè)狀態(tài)轉(zhuǎn)移方程 f(n)，就能很快寫(xiě)出問(wèn)題的遞歸實(shí)現(xiàn)方法。把大問(wèn)題變成幾個(gè)小問(wèn)題，在幾個(gè)小問(wèn)題中求出最佳解。」

「重疊子問(wèn)題：比如斐波那契數(shù)列中的f(5)，算了f(4)和f(3)，結(jié)果f(4)又給Runsen算了一次f(3)。其實(shí)就是將一棵二叉樹(shù)進(jìn)行剪枝操作，方法是備忘錄來(lái)存儲(chǔ)在內(nèi)存上?！?/p>

「自下而上：反過(guò)來(lái)求解」

動(dòng)態(tài)規(guī)劃思路

動(dòng)態(tài)規(guī)劃是一種求問(wèn)題最優(yōu)解的方法。通用的思路：將問(wèn)題的解轉(zhuǎn)化成==> 求解子問(wèn)題，==> 遞推，==>最小子問(wèn)題為可直接獲得的初始狀態(tài)。

詳細(xì)的步驟下面所示：

判斷是否可用遞歸來(lái)解，可以的話(huà)進(jìn)入步驟 2

分析在遞歸的過(guò)程中是否存在大量的重復(fù)子問(wèn)題

采用備忘錄的方式來(lái)存子問(wèn)題的解以避免大量的重復(fù)計(jì)算(剪枝)

改用自底向上的方式來(lái)遞推，即動(dòng)態(tài)規(guī)劃

關(guān)鍵就是「找狀態(tài)轉(zhuǎn)移方程」。

斐波那契數(shù)列和爬樓梯問(wèn)題

斐波那契數(shù)列最早從兔子問(wèn)題演變過(guò)來(lái)的，

假設(shè)一對(duì)初生兔子一個(gè)月到成熟期，一對(duì)成熟兔子每月生一對(duì)兔子，并且一年內(nèi)沒(méi)有發(fā)生死亡。那么，由一對(duì)初生兔子開(kāi)始 一年以后可以繁殖多少對(duì)兔子?

我們直接看下面的圖

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233……

發(fā)現(xiàn)以上規(guī)律是，每月的兔子對(duì)數(shù)=上一月的兔子對(duì)數(shù)+該月新生的兔子對(duì)數(shù)=上一月的兔子對(duì)數(shù)+上上月的兔子對(duì)數(shù)

得到序列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233……

這個(gè)序列即為斐波那契數(shù)列“(Fibonacci sequence)”。斐波那契數(shù)列中的任一個(gè)數(shù)，都叫斐波那契數(shù)

斐波那契數(shù)列，通常都是用來(lái)講解遞歸函數(shù)，嘗試用遞歸的思路來(lái)解決，但是時(shí)間復(fù)雜度高達(dá)。

 
 
 
 
      
  
  
  
  1. def fib(n): 
    2.   
  
  
  
  2.   if n <= 1: 
    3.   
  
  
  
  3.       return 1 
    4.   
  
  
  
  4.   return fib(n-1) + fib(n-2) 
    5.   
  
  
  
  5.  
    6.   
  
  
  
  6. for i in range(20): 
    7.   
  
  
  
  7.     print(fib(i), end=' ') 
    8.

但是，我們發(fā)現(xiàn)時(shí)間復(fù)雜度高達(dá)，最主要的原因是存在重復(fù)計(jì)算。比如fib(3) 會(huì)計(jì)算 fib(2) + fib(1)， 而 fib(2) 又會(huì)計(jì)算 fib(1) + fib(0)。

這個(gè) fib(1) 就是完全重復(fù)的計(jì)算，不應(yīng)該為它再遞歸調(diào)用一次，而是應(yīng)該在第一次求解除它了以后，就把他“記憶”下來(lái)。

這就是備忘錄解法，用空間來(lái)?yè)Q取時(shí)間的思路。把已經(jīng)求得的解放在字典Map或者列表list 里，下次直接取，而不去重復(fù)結(jié)算。

備忘錄解法的代碼和動(dòng)態(tài)規(guī)劃的代碼和思路基本一致。

斐波那契數(shù)列在Leetcode也有一題類(lèi)似的，這是Leetcode第70題. 爬樓梯，每次你可以爬 1 或 2 個(gè)臺(tái)階。你有多少種不同的方法可以爬到樓頂呢?

注意：給定 n 是一個(gè)正整數(shù)。

 
 
 
 
      
  
  
  
  1. 輸入：2 
    2.   
  
  
  
  2. 輸出：2 
    3.   
  
  
  
  3. 解釋?zhuān)?nbsp;有兩種方法可以爬到樓頂。 
    4.   
  
  
  
  4. 1.  1 階 + 1 階 
    5.   
  
  
  
  5. 2.  2 階 
    6.

斐波那契數(shù)列和爬樓梯問(wèn)題的狀態(tài)轉(zhuǎn)移方程都是:dp[i] = dp[i-1] +dp[i-2]。但是需要初始化dp，不然回報(bào)list assignment index out of range的錯(cuò)誤。

下面就是斐波那契數(shù)列問(wèn)題 爬樓梯的解決代碼，也是Leetcode70題的解決代碼。

 
 
 
 
      
  
  
  
  1. class Solution: 
    2.   
  
  
  
  2.     def Fibonacci(self, n): 
    3.   
  
  
  
  3.         if n == 0: 
    4.   
  
  
  
  4.             return 1 
    5.   
  
  
  
  5.         if n == 1: 
    6.   
  
  
  
  6.             return 1 
    7.   
  
  
  
  7.         if n > 1: 
    8.   
  
  
  
  8.             dp = [0] * (n+1) 
    9.   
  
  
  
  9.             dp[0] = 1  
    10.   
  
  
  
  10.             dp[1]= 1 
    11.   
  
  
  
  11.             for i in range(2,n+1): 
    12.   
  
  
  
  12.                 dp[i] = dp[i-1] +dp[i-2] 
    13.   
  
  
  
  13.             return dp[n] 
    14.

Leetcode53 最大子序和

最大子序和，Runsen記得很清楚是Leetcode的53題。

 
 
 
 
      
  
  
  
  1. 輸入: [-2,1,-3,4,-1,2,1,-5,4], 
    2.   
  
  
  
  2. 輸出: 6 
    3.   
  
  
  
  3. 解釋: 連續(xù)子數(shù)組 [4,-1,2,1] 的和最大，為 6。 
    4.

聲明兩個(gè)變量, currentSum: 之前連續(xù)幾個(gè)值相加的和, maxSum: 當(dāng)前最大的子序列和。最大子序和狀態(tài)轉(zhuǎn)移方程 f(i) = max(f(i), f(i)+nums[i+1])

 
 
 
 
      
  
  
  
  1. def maxSubArray(nums) : 
    2.   
  
  
  
  2.     '''查找連續(xù)子數(shù)組的最大和 
    3.   
  
  
  
  3.  
    4.   
  
  
  
  4.     Args: 
    5.   
  
  
  
  5.         nums: 整數(shù)數(shù)組 
    6.   
  
  
  
  6.  
    7.   
  
  
  
  7.     Returns: 
    8.   
  
  
  
  8.         返回整數(shù)數(shù)組的最大子序和 
    9.   
  
  
  
  9.     ''' 
    10.   
  
  
  
  10.     # 比較當(dāng)前子序和，最大子序和，返回最大值 
    11.   
  
  
  
  11.  
    12.   
  
  
  
  12.     # 定義當(dāng)前子序和以及最大子序和為第一個(gè)元素 
    13.   
  
  
  
  13.     cursum = maxsum = nums[0] 
    14.   
  
  
  
  14.     for i in range(1, len(nums)): 
    15.   
  
  
  
  15.         cursum = max(nums[i], cursum + nums[i]) 
    16.   
  
  
  
  16.         print(cursum) 
    17.   
  
  
  
  17.         # 比較當(dāng)前值和定義的最大子序和值，將最大值重置賦值給 max_sum 
    18.   
  
  
  
  18.         maxsum = max(cursum, maxsum) 
    19.   
  
  
  
  19.         print(maxsum) 
    20.   
  
  
  
  20.     return maxsum 
    21.   
  
  
  
  21.  
    22.   
  
  
  
  22. print(maxSubArray([-2,1,-3,4,-1,2,1,-5,4])) 
    23.

前面只是動(dòng)態(tài)規(guī)劃的熱身，Runsen先進(jìn)入「三個(gè)背包問(wèn)題的強(qiáng)化系列」，01背包問(wèn)題才是動(dòng)態(tài)規(guī)劃的入門(mén)階段。

01背包問(wèn)題

對(duì)應(yīng)的題目：https://www.acwing.com/problem/content/2/

01背包問(wèn)題就是物品只有一件。

 
 
 
 
      
  
  
  
  1. 輸入格式 : 第一行兩個(gè)整數(shù)，N，V，用空格隔開(kāi)，分別表示物品數(shù)量和背包容積。接下來(lái)有 N 行，每行兩個(gè)整數(shù) vi,wi，用空格隔開(kāi)，分別表示第 i 件物品的體積和價(jià)值。  
    2.   
  
  
  
  2. 輸出格式 : 輸出一個(gè)整數(shù)，表示最大價(jià)值。  
    3.   
  
  
  
  3. 數(shù)據(jù)范圍 : 0

 輸入樣例

 
 
 
 
      
  
  
  
  1. 4 5 
    2.   
  
  
  
  2. 1 2 
    3.   
  
  
  
  3. 2 4 
    4.   
  
  
  
  4. 3 4 
    5.   
  
  
  
  5. 4 6 
    6.

輸出樣例：

 
 
 
 
      
  
  
  
  1. 8 # 4+4 2+6 
    2.

在解決這類(lèi)問(wèn)題先，dp怎么定義和狀態(tài)轉(zhuǎn)移方程怎么搞就是重要，搞定了就是半分鐘的事情。搞不定了可能半小時(shí)的事情。

很多人和Runsen一樣，都會(huì)把狀態(tài)定義二維數(shù)組：為前i「?jìng)€(gè)」 物品中，體積恰好為v 時(shí)的最大價(jià)值。

狀態(tài)轉(zhuǎn)移方程也是順便搞定：

如果 「不選第 i 個(gè)物品」，那么前 i 個(gè)背包的最大價(jià)值就是前 i-1 個(gè)物品的價(jià)值，即 dp[i][j] = dp[i-1][j];

如果 「選擇了第 i 個(gè)物品」，前 i-1 個(gè)物品的體積就是j - weight[i]，狀態(tài)方程為 dp[i - 1][j - weight[i]] + value[i]，注意這時(shí)的價(jià)值是前i-1個(gè)物品的價(jià)值，因此少了 weight[i]]的空間，所以 dp[i - 1][j - weight[i]] + value[i]。

 
 
 
 
      
  
  
  
  1. ''' 
    2.   
  
  
  
  2. @Author：Runsen 
    3.   
  
  
  
  3. @WeChat：RunsenLiu  
    4.   
  
  
  
  4. @微信公眾號(hào)：Python之王 
    5.   
  
  
  
  5. @CSDN：https://blog.csdn.net/weixin_44510615 
    6.   
  
  
  
  6. @Github：https://github.com/MaoliRUNsen 
    7.   
  
  
  
  7. @Date：2020/9/10 
    8.   
  
  
  
  8. ''' 
    9.   
  
  
  
  9. # n是個(gè)數(shù) v是體積  # 4 5 
    10.   
  
  
  
  10. n, v = map(int, input().split()) 
    11.   
  
  
  
  11. goods = [] 
    12.   
  
  
  
  12. for i in range(n): 
    13.   
  
  
  
  13.     goods.append([int(i) for i in input().split()]) 
    14.   
  
  
  
  14.  
    15.   
  
  
  
  15. # 初始化，先全部賦值為0，這樣至少體積為0或者不選任何物品的時(shí)候是滿(mǎn)足要求 
    16.   
  
  
  
  16. # 因?yàn)閒or 循環(huán)先遍歷個(gè)數(shù)，所以將體積寫(xiě)在里面 
    17.   
  
  
  
  17. dp = [[0 for i in range(v+1)] for j in range(n+1)] 
    18.   
  
  
  
  18. print(goods) # [[1, 2], [2, 3], [3, 4], [4, 5]] 
    19.   
  
  
  
  19. # 0 可以無(wú)視掉 
    20.   
  
  
  
  20. for i in range(1, n+1): 
    21.   
  
  
  
  21.     for j in range(1,v+1): 
    22.   
  
  
  
  22.         # 判斷背包容量是不是大于第i件物品的體積 
    23.   
  
  
  
  23.         if j>=goods[i-1][0]: 
    24.   
  
  
  
  24.             # 在選和不選的情況中選出最大值 
    25.   
  
  
  
  25.             dp[i][j] = max(dp[i-1][j], dp[i - 1][j - goods[i - 1][0]] + goods[i - 1][1]) 
    26.   
  
  
  
  26.         else: 
    27.   
  
  
  
  27.             # 第i個(gè)物品不選 
    28.   
  
  
  
  28.             dp[i][j] = dp[i-1][j]   
    29.   
  
  
  
  29. print(dp) 
    30.   
  
  
  
  30. print(dp[-1][-1]) 
    31.   
  
  
  
  31.  
    32.   
  
  
  
  32. # 測(cè)試數(shù)據(jù) 
    33.   
  
  
  
  33. 5 10 
    34.   
  
  
  
  34. 1 2 
    35.   
  
  
  
  35. 2 3 
    36.   
  
  
  
  36. 3 4 
    37.   
  
  
  
  37. 4 5 
    38.   
  
  
  
  38. 5 6 
    39.   
  
  
  
  39. [[1, 2], [2, 3], [3, 4], [4, 5], [5, 6]] 
    40.   
  
  
  
  40. [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2], [0, 2, 3, 5, 5, 5, 5, 5, 5, 5, 5], [0, 2, 3, 5, 6, 7, 9, 9, 9, 9, 9], [0, 2, 3, 5, 6, 7, 9, 10, 11, 12, 14], [0, 2, 3, 5, 6, 7, 9, 10, 11, 12, 14]] 
    41.   
  
  
  
  41. 14  # 2+3+4+5 
    42.

上面代碼，如果知道了dp怎么定義和狀態(tài)轉(zhuǎn)移方程，那么和Runsen寫(xiě)的一樣快，其實(shí)那時(shí)Runsen寫(xiě)得挺慢得，說(shuō)不定你比Runsen還厲害。

上面的代碼是狀態(tài)定義二維數(shù)組，有的大佬竟然可以把狀態(tài)定義一維數(shù)組，這樣空間就節(jié)省了。「Runsen都百思不知其解」。只能說(shuō)Runsen真的挺菜的。只好勤能補(bǔ)拙!

一維數(shù)組就是去掉了狀態(tài)，且的遍歷方式改為 「倒序」 遍歷到 c[i]。

因此，Runsen們可以將求解空間進(jìn)行優(yōu)化，將二維數(shù)組壓縮成一維數(shù)組，此時(shí)，轉(zhuǎn)移方程變?yōu)椋?/p>

 
 
 
 
      
  
  
  
  1. ''' 
    2.   
  
  
  
  2. @Author：Runsen 
    3.   
  
  
  
  3. @WeChat：RunsenLiu  
    4.   
  
  
  
  4. @微信公眾號(hào)：Python之王 
    5.   
  
  
  
  5. @CSDN：https://blog.csdn.net/weixin_44510615 
    6.   
  
  
  
  6. @Github：https://github.com/MaoliRUNsen 
    7.   
  
  
  
  7. @Date：2020/9/10 
    8.   
  
  
  
  8. ''' 
    9.   
  
  
  
  9. n, v = map(int, input().split()) 
    10.   
  
  
  
  10. goods = [] 
    11.   
  
  
  
  11. for i in range(n): 
    12.   
  
  
  
  12.     goods.append([int(i) for i in input().split()]) 
    13.   
  
  
  
  13. print(goods) # [[1, 2], [2, 3], [3, 4], [4, 5], [5, 6]] 
    14.   
  
  
  
  14. dp = [0 for i in range(v + 1)] 
    15.   
  
  
  
  15. for i in range(n): 
    16.   
  
  
  
  16.     # 由于要放入物品，所以從空間v開(kāi)始遍歷到0 
    17.   
  
  
  
  17.     for j in range(v, -1, -1): 
    18.   
  
  
  
  18.         # 判斷背包容量是不是大于第i件物品的體積 
    19.   
  
  
  
  19.         if j >= goods[i][0]: 
    20.   
  
  
  
  20.             # 更新j的狀態(tài)，即當(dāng)前容量放入物品之后的狀態(tài) 
    21.   
  
  
  
  21.             dp[j] = max(dp[j], dp[j - goods[i][0]] + goods[i][1]) 
    22.   
  
  
  
  22. print(dp) 
    23.   
  
  
  
  23. print(dp[-1]) 
    24.   
  
  
  
  24.  
    25.   
  
  
  
  25. 5 10 
    26.   
  
  
  
  26. 1 2 
    27.   
  
  
  
  27. 2 3 
    28.   
  
  
  
  28. 3 4 
    29.   
  
  
  
  29. 4 5 
    30.   
  
  
  
  30. 5 6 
    31.   
  
  
  
  31. [[1, 2], [2, 3], [3, 4], [4, 5], [5, 6]] 
    32.   
  
  
  
  32. [0, 2, 3, 5, 6, 7, 9, 10, 11, 12, 14] 
    33.   
  
  
  
  33. 14 
    34.

上面就是01背包的最終解決方法，由于文章有限，多重背包，完全背包將在之后的博客進(jìn)行書(shū)寫(xiě)!!!

不知不覺(jué)現(xiàn)在寫(xiě)了幾天，代碼反復(fù)寫(xiě)，寫(xiě)完寫(xiě)博客，真心累!誰(shuí)叫自己的算法比較弱!

希望以后遇到01背包的問(wèn)題，就是在恐怖的算法面試中遇見(jiàn)了Runsen的愛(ài)情!

參考資料

[1]傳送門(mén)~:https://github.com/MaoliRUNsen/runsenlearnpy100


網(wǎng)頁(yè)名稱(chēng)：從斐波那契數(shù)列和零一背包問(wèn)題探究動(dòng)態(tài)規(guī)劃
轉(zhuǎn)載來(lái)源：http://m.5511xx.com/article/djscgoj.html