深入淺出動態規劃演算法(上)
開啟掘金成長之旅!這是我參與「掘金日新計劃 · 12 月更文挑戰」的第24天,點選檢視活動詳情。
一,動態規劃概念
動態規劃比較適合用來求解最優問題,比如求最大值、最小值等等。它可以非常顯著地降低時間複雜度,提高程式碼的執行效率。
它和遞迴一樣都非常難學,主要學習難點在於求解問題的過程不太符合人類常規的思維方式。
二,0-1 揹包問題
對於一組不同重量、不可分割的物品,我們需要選擇一些裝入揹包,在滿足揹包最大重量限制的前提下,揹包中物品總重量的最大值是多少呢?
關於這個 0-1
揹包問題,上一節學習了回溯的解決方法,也就是窮舉搜尋所有可能的裝法(時間複雜度指數級),然後找出滿足條件的最大值。有沒有什麼規律,可以有效降低時間複雜度呢?
1,回溯法的求解過程:
直接看程式碼,規律是不好的,畫個求解過程圖(遞迴樹)會好看些。假設揹包的最大承載重量是 9
,有 5
個不同的物品,每個物品的重量分別是 2,2,4,6,3
。求解過程的遞迴樹如下圖所示。
遞迴樹中的每個節點表示一種狀態,我們用(i, cw)
來表示。其中,i
表示將要決策第幾個物品是否裝入揹包,cw
表示當前揹包中物品的總重量。比如,(2,2)
表示我們將要決策第 2
個物品是否裝入揹包,在決策前,揹包中物品的總重量是 2
。這裡使用回溯演算法,從遞迴樹中可以發現其中有些子問題的求解是重複的,且時間複雜度是指數級的。
使用”備忘錄”(記憶化遞迴)的解決方式,記錄已經計算好的 f(i, cw)
,當再次計算到重複的 f(i, cw)
的時候,可以直接從備忘錄中取出來用,就不用再遞迴計算了,這樣就可以避免冗餘計算。
```cpp int maxW = 0; int weight[6] = {2,2,4,6,3}; // 物品重量 int n = 5; // 物品個數 int w = 9; // 揹包承受的最大重量 bool mem[5][10]; // 備忘錄,預設值false
// 記憶化遞迴演算法實現 class SolutionBacktracking{ public: void f(int i, int cw){ // i 表示放第 i 個物品,cw 表示當前裝進揹包的物品的重量和 if (cw == w || i == n) { // cw==w表示裝滿了,i==n表示物品都考察完了 if(cw > maxW) maxW = cw; return; } if(mem[i][cw]) return; // 重複狀態 mem[i][cw] = true; // 記錄狀態
f(i+1, cw); // 不放第 i 個物品
if(cw+weight[i] <= w)
f(i+1, cw+weight[i]); // 放第 i 個物品
}
}; ```
這裡依然是基於回溯演算法實現的,但是採用了記憶化遞迴的方法,時間複雜度和空間複雜度都是 $O(n*(w+1))$,$n$ 為物品個數,$w$ 表示揹包承受的最大重量。
2,動態規劃求解過程如下:
把整個求解過程分為 n
個階段,每個階段會決策一個物品是否放到揹包中。每個物品決策(放入或者不放入揹包)完之後,揹包中的物品的重量會有多種情況,也就是說,會達到多種不同的狀態,對應到遞迴樹中,就是有很多不同的節點。
我們把每一層重複的狀態(節點)合併,只記錄不同的狀態,然後基於上一層的狀態集合,來推導下一層的狀態集合。我們可以通過合併每一層重複的狀態,這樣就保證每一層不同狀態的個數都不會超過 w
個(w 表示揹包的承載重量),也就是例子中的 9
。於是,我們就成功避免了每層狀態個數的指數級增長。動態規劃方法的計算過程如下圖:
我們用一個二維陣列 states[n][w+1]
,來記錄每層可以達到的不同狀態。0-1
揹包問題的動態規劃解法的 C++
程式碼如下:
```cpp
class SolutionDP1{
public:
// weight:物品重量,n:物品個數,w:揹包可承載重量
int knapsack1(int weight[], int n, int w){
vector
// 在最後一層變數找到最接近 w 的重量並輸出結果
for(int i=w; i>0; i--){
if(states[n-1][i]) return i;
}
return 0;
}
}; ```
這就是一種用動態規劃解決問題的思路。我們把問題分解為多個階段,每個階段對應一個決策。我們記錄每一個階段可達的狀態集合(去掉重複的),然後通過當前階段的狀態集合,來推導下一個階段的狀態集合,動態地往前推進。這也是動態規劃這個名字的由來,你可以自己體會一下
首先,可以分解為多階段,其次,狀態去重,最後當前階段可以利用上一個階段來獲取。這是動態規劃的關鍵。
我們知道回溯演算法解決這個問題的時間複雜度是 $O(2^n)$、指數級,那動態規劃解決方案的時間複雜度是多少呢?來分析一下,這個程式碼的時間複雜度非常好分析,耗時最多的部分就是程式碼中的兩層 for
迴圈,所以時間複雜度是 $O(n*w)$。$n$ 表示物品個數,$w$ 表示揹包可以承載的總重量。
雖然動態規劃的時間效率較高,但是空間複雜度為 $O(n*w)$,對空間消耗比較大。我們可以考慮用一個大小為 $w+1$ 的一維陣列代替二維陣列,減少記憶體消耗。程式碼如下:
```cpp
class SolutionDP2{
public:
// weight:物品重量,n:物品個數,w:揹包可承載重量
int knapsack2(int weight[], int n, int w){
vector
// 動態規劃-分階段
for(int i=1; i<n;i++){
for(int j=w-weight[i]; j>=0; j--) { // 第 i 個物品放進揹包
if(states[j]) states[j+weight[i]] = true;
}
}
// 在最後一層變數找到最接近 w 的重量並輸出結果
for(int i=w;i>0;i--){
if(states[i]) return i;
}
return 0;
}
}; ```
程式分析:遍歷每個物品,將該物品放入揹包時,在不超過最大重量的前提下,再遍歷檢視之前的放入記錄,將之前可能出現的重量的和當前物品的重量相加再記錄下來,等所有方案都嘗試過後,可能出現的揹包重量也都被記錄下來了,最後,從中選擇一個最大值返回。
三,0-1 揹包問題升級版
前面講的揹包問題,只涉及揹包重量和物品重量。現在引入物品價值這一變數。對於一組不同重量、不同價值、不可分割的物品,我們選擇將某些物品裝入揹包,在滿足揹包最大重量限制的前提下,揹包中可裝入物品的總價值最大是多少呢?
1,這個問題依舊可以先用回溯演算法來解決,程式碼如下:
```cpp // 0-1 揹包問題升級版的回溯解法 int maxV = 0; // 結果放到maxV中 int weight[] = {2,2,4,6,3}; // 物品的重量 int value[] = {3,4,8,9,6}; // 物品的價值 int n = 5; // 物品個數 int w = 9; // 揹包承受的最大重量
class Solution{ public: void f(int i, int cw, int cv) { // 呼叫f(0, 0, 0) if (cw == w || i == n) { // cw==w表示裝滿了,i==n表示物品都考察完了 if(cv > maxV) maxV = cv; return; } if(cv > maxV) maxV = cv; f(i+1, cw, cv); // 不放第 i 個物品 if(cw+weight[i] <= w) f(i+1, cw+weight[i], cv+value[i]) // 放第 i 個物品 } }; ```
2,使用動態規劃解決這個問題更高效。把整個求解過程分為 $n$ 個階段,每個階段會決策一個物品是否放到揹包中。每個階段決策完之後,揹包中的物品的總重量以及總價值,會有多種情況,也就是會達到多種不同的狀態。我們用一個二維陣列 states[n][w+1]
,來記錄每層可以達到的不同狀態。
```cpp
class SolutionDP3{
int knapsack3(int weight[], int value[], int n, int w) {
vector
for(int i=1; i<n; i++){
for(int j=0; j< w; j++){ // 不放入第 i 個物品
if(states[i-1][j]) states[i][j] = states[i-1][j];
}
for(int j=0; j< w-weight[i]; j++){ // 放入第 i 個物品
int v = states[i-1][j] + values;
if(v > states[i][j+weight[i]])
states[i][j+weight[i]] = v;
}
}
int maxV = -1;
for(int j = w; j>=0; j--){
if(states[n-1][j] > maxV) maxV = states[n-1][j];
}
return maxV;
}
} ```
程式碼的時間複雜度是 $O(n\cdot w)$,空間複雜度也是 $O(n\cdot w)$。
四,總結
大部分動態規劃能解決的問題,都可以通過回溯演算法來解決,只不過回溯演算法解決起來效率比較低,時間複雜度是指數級的。動態規劃演算法,在執行效率方面,要高很多。儘管執行效率提高了,但是動態規劃的空間複雜度也提高了,所以,很多時候,我們會說,動態規劃是一種空間換時間的演算法思想。
五,練習題
5.1,leetcode322 零錢兌換
給你一個整數陣列 coins
,表示不同面額的硬幣;以及一個整數 amount
,表示總金額。計算並返回可以湊成總金額所需的 最少的硬幣個數 。如果沒有任何一種硬幣組合能組成總金額,返回 -1
。
你可以認為每種硬幣的數量是無限的。
動態規劃解法的 C++
程式碼如下:
cpp
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
int Max = amount + 1;
vector<int> dp(amount + 1, Max);
dp[0] = 0;
for (int i = 1; i <= amount; ++i) {
for (int j = 0; j < (int)coins.size(); ++j) {
if (coins[j] <= i) {
dp[i] = min(dp[i], dp[i - coins[j]] + 1);
}
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
};
參考資料
- ssh遠端連線方式總結
- 深度學習基礎-損失函式詳解
- 模型壓縮-剪枝演算法詳解
- 機器學習經典演算法總結
- 深度學習基礎-優化演算法詳解
- 深度學習基礎-機器學習基本原理
- 機器學習基本概念總結
- 手把手教你註冊和使用ChatGPT
- 深入淺出動態規劃演算法(中)
- 深度學習煉丹-資料預處理和增強
- 深入淺出回溯演算法
- 深入淺出動態規劃演算法(上)
- GitHub 車牌檢測識別專案調研
- 卷積神經網路壓縮方法總結
- 神經網路模型複雜度分析
- MobileNetv1 論文詳解
- ShuffleNetv2論文詳解
- Pytorch基礎-tensor資料結構
- Fast YOLO:用於實時嵌入式目標檢測(附論文下載)
- 嵌入式新聞早班車-第24期