日本综合一区二区|亚洲中文天堂综合|日韩欧美自拍一区|男女精品天堂一区|欧美自拍第6页亚洲成人精品一区|亚洲黄色天堂一区二区成人|超碰91偷拍第一页|日韩av夜夜嗨中文字幕|久久蜜综合视频官网|精美人妻一区二区三区

RELATEED CONSULTING
相關咨詢
選擇下列產品馬上在線溝通
服務時間：8:30-17:00
你可能遇到了下面的問題
關閉右側工具欄

新聞中心

這里有您想知道的互聯網營銷解決方案
從斐波那契數列和零一背包問題探究動態(tài)規(guī)劃

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

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

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

極客時間超哥的動態(tài)規(guī)劃、拉勾教育的算法專欄。Runsen真的不想在動態(tài)規(guī)劃，死一次又一次。死了N次，學了N次，就是他媽的寫不出來。

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

三個背包問題：01背包，多重背包，完全背包。

動態(tài)規(guī)劃前置知識

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

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

「最優(yōu)子結構：一般由最優(yōu)子結構，推導出一個狀態(tài)轉移方程 f(n)，就能很快寫出問題的遞歸實現方法。把大問題變成幾個小問題，在幾個小問題中求出最佳解?！?/p>

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

「自下而上：反過來求解」

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

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

詳細的步驟下面所示：

判斷是否可用遞歸來解，可以的話進入步驟 2

分析在遞歸的過程中是否存在大量的重復子問題

采用備忘錄的方式來存子問題的解以避免大量的重復計算(剪枝)

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

關鍵就是「找狀態(tài)轉移方程」。

斐波那契數列和爬樓梯問題

斐波那契數列最早從兔子問題演變過來的，

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

我們直接看下面的圖

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

發(fā)現以上規(guī)律是，每月的兔子對數=上一月的兔子對數+該月新生的兔子對數=上一月的兔子對數+上上月的兔子對數

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

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

斐波那契數列，通常都是用來講解遞歸函數，嘗試用遞歸的思路來解決，但是時間復雜度高達。

 
 
 
 
      
  
  
  
  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ā)現時間復雜度高達，最主要的原因是存在重復計算。比如fib(3) 會計算 fib(2) + fib(1)， 而 fib(2) 又會計算 fib(1) + fib(0)。

這個 fib(1) 就是完全重復的計算，不應該為它再遞歸調用一次，而是應該在第一次求解除它了以后，就把他“記憶”下來。

這就是備忘錄解法，用空間來換取時間的思路。把已經求得的解放在字典Map或者列表list 里，下次直接取，而不去重復結算。

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

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

注意：給定 n 是一個正整數。

 
 
 
 
      
  
  
  
  1. 輸入：2 
    2.   
  
  
  
  2. 輸出：2 
    3.   
  
  
  
  3. 解釋： 有兩種方法可以爬到樓頂。 
    4.   
  
  
  
  4. 1.  1 階 + 1 階 
    5.   
  
  
  
  5. 2.  2 階 
    6.

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

下面就是斐波那契數列問題 爬樓梯的解決代碼，也是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ù)子數組 [4,-1,2,1] 的和最大，為 6。 
    4.

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

 
 
 
 
      
  
  
  
  1. def maxSubArray(nums) : 
    2.   
  
  
  
  2.     '''查找連續(xù)子數組的最大和 
    3.   
  
  
  
  3.  
    4.   
  
  
  
  4.     Args: 
    5.   
  
  
  
  5.         nums: 整數數組 
    6.   
  
  
  
  6.  
    7.   
  
  
  
  7.     Returns: 
    8.   
  
  
  
  8.         返回整數數組的最大子序和 
    9.   
  
  
  
  9.     ''' 
    10.   
  
  
  
  10.     # 比較當前子序和，最大子序和，返回最大值 
    11.   
  
  
  
  11.  
    12.   
  
  
  
  12.     # 定義當前子序和以及最大子序和為第一個元素 
    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.         # 比較當前值和定義的最大子序和值，將最大值重置賦值給 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.

前面只是動態(tài)規(guī)劃的熱身，Runsen先進入「三個背包問題的強化系列」，01背包問題才是動態(tài)規(guī)劃的入門階段。

01背包問題

對應的題目：https://www.acwing.com/problem/content/2/

01背包問題就是物品只有一件。

 
 
 
 
      
  
  
  
  1. 輸入格式 : 第一行兩個整數，N，V，用空格隔開，分別表示物品數量和背包容積。接下來有 N 行，每行兩個整數 vi,wi，用空格隔開，分別表示第 i 件物品的體積和價值。  
    2.   
  
  
  
  2. 輸出格式 : 輸出一個整數，表示最大價值。  
    3.   
  
  
  
  3. 數據范圍 : 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.

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

很多人和Runsen一樣，都會把狀態(tài)定義二維數組：為前i「個」 物品中，體積恰好為v 時的最大價值。

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

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

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

 
 
 
 
      
  
  
  
  1. ''' 
    2.   
  
  
  
  2. @Author：Runsen 
    3.   
  
  
  
  3. @WeChat：RunsenLiu  
    4.   
  
  
  
  4. @微信公眾號：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是體積  # 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或者不選任何物品的時候是滿足要求 
    16.   
  
  
  
  16. # 因為for 循環(huán)先遍歷個數，所以將體積寫在里面 
    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 可以無視掉 
    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個物品不選 
    28.   
  
  
  
  28.             dp[i][j] = dp[i-1][j]   
    29.   
  
  
  
  29. print(dp) 
    30.   
  
  
  
  30. print(dp[-1][-1]) 
    31.   
  
  
  
  31.  
    32.   
  
  
  
  32. # 測試數據 
    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)轉移方程，那么和Runsen寫的一樣快，其實那時Runsen寫得挺慢得，說不定你比Runsen還厲害。

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

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

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

 
 
 
 
      
  
  
  
  1. ''' 
    2.   
  
  
  
  2. @Author：Runsen 
    3.   
  
  
  
  3. @WeChat：RunsenLiu  
    4.   
  
  
  
  4. @微信公眾號：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開始遍歷到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)，即當前容量放入物品之后的狀態(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背包的最終解決方法，由于文章有限，多重背包，完全背包將在之后的博客進行書寫!!!

不知不覺現在寫了幾天，代碼反復寫，寫完寫博客，真心累!誰叫自己的算法比較弱!

希望以后遇到01背包的問題，就是在恐怖的算法面試中遇見了Runsen的愛情!

參考資料

[1]傳送門~:https://github.com/MaoliRUNsen/runsenlearnpy100


網站欄目：從斐波那契數列和零一背包問題探究動態(tài)規(guī)劃
鏈接地址：http://www.dlmjj.cn/article/djscgoj.html