動態規劃(Dynamic Programming)

# 動態規劃(Dynamic Programming) - 空間換取時間 - 將運算過且會重複利用到的值存起來 --- ## 費氏數列 - $F_0=0$ - $F_1=1$ - $F_n=F_{n-1}+F_{n-2} (2 \le n)$ ---- ## Bottom-up ```cpp= int x; long long dp[51]; dp[0] = 0; dp[1] = 1; for (int i = 2; i <= 50; i++) dp[i] = dp[i - 1] + dp[i - 2]; cin >> x cout << dp[x]; ``` ---- ## Top-down ```cpp= long long dp[51]; int F(int n) { if (n == 0) return 0; if (n == 1) return 1; if (dp[n] != 0) return dp[n]; return dp[n] = F(n - 1) + F(n - 2); } int main() { int x; cin >> x; cout << F(x); return 0; } ``` ---- ![](https://i.imgur.com/hOqpUnj.gif) --- ## 0/1背包問題 將一群物品儘量塞進背包裡面，令背包裡面的物品總價值最高。背包沒有容量限制，無論物品是什麼形狀大小，都能塞進背包；但是背包有重量限制，如果物品太重，就會撐破背包。 ----  ### 範例 | 物品 | 價值 | 體積 | | --- | ---- | -- | | A | 5 | 11 | | B | 3 | 10 | | C | 2 | 7 | 體積限制：7 1. 按照CP值取 2. ----  ### 範例 | 物品 | 價值 | 體積 | | --- | ---- | -- | | A | 5 | 11 | | B | 3 | 10 | | C | 2 | 7 | 體積限制：7 1. ~~按照CP值取~~ 2.  窮舉 ---- ### 優化! - 由於每個物品分為取或不取 → 計算次數約為$2^n$ - 動態規劃!!(運算次數為 $n \cdot w_{max}$) ---- ### 動態規劃令陣列$dp[i][j]$為在 *選取第$i$項物品* 時， *$選取物品重量 \le j$* 的最大價值。 - $1 \le i \le n$ - $1 \le j \le w_{max}$ 且$v[i]$為第$i$項的價值，$w[i]$為第$i$項的重量 ---- 經過思考後，可以推出以下轉移式： $dp[i][j]=$ $\left\{ \begin{array}{l} dp[i-1][j] \text{................................................}(j < w[i])\\ max(dp[i - 1][j], dp[i-1][j-w[i]]+v[i]\text{..}(j \ge w[i])\end{array} \right .$ ---- ### 解說 $dp[i][j] = max(dp[i - 1][j],\text{ } dp[i - 1][j - w[i]] + v[i])$ 1. 不選取： $dp[i - 1][j]$代表的是第$i$項不選取時 *$總重量 \le j$* 的最大值 2. 　選取： $dp[i - 1][j - w[i]] + v[i]$選取此物品時 *$總重量 \le j$* 的最大值 舉例：$i=3, j=10, w[i]=6, v[i]=5$。 則$i-1=2, \text{ }j-w[i]=4$。 $dp[i-1][j-w[i]]+v[i] = dp[2][4]+5$。 ---- ### ZeroJudge d637 第一行有正整數$n(1 < n \le 10000)$表有n顆鴨飼料接下來的$n$行，每行有$ab$兩個正整數， $a$代表這顆鴨飼料的體積，$b$代表飽足感$(1 \le a \le 100 , 1 \le b \le 5000)$ 並且鴨子最多可以吃滿100體積的飼料。請輸出最大飽足感為何。 ---- - 範例輸入： ``` 6 10 8 25 25 65 75 25 29 25 17 15 20 ``` - 範例輸出： ``` 112 (選取第1,3,4項) ``` ---- #### 程式碼 ```cpp= #include <iostream> using namespace std; const int maxn = 10000 + 1; const int w_max = 100; int dp[maxn][w_max + 1], w[maxn], v[maxn], n, ans; int main() { cin >> n; for (int i = 1; i <= n; i++) cin >> w[i] >> v[i]; for (int i = 1; i <= n; i++) { for (int j = 1; j < w[i]; j++) dp[i][j] = dp[i - 1][j]; for (int j = w[i]; j <= w_max; j++) dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]); } cout << dp[n][w_max]; return 0; } ``` ---- #### 補充根據以上程式碼，可以透過「滾動」的技巧來降低陣列大小，因只會存取到$dp[i]和dp[i-1]$，更以前的值不需要則可令 $\left\{ \begin{array}{l} dp[i]=dp[i\text{%}2]=dp[i\text{&}1]\\ dp[i-1]=dp[(i-1) \text{%}2] =dp[!(i\text{&}1)]\end{array} \right .$ ---- 則程式碼可變成如下： ```cpp= #include <iostream> using namespace std; const int maxn = 10000 + 1; const int w_max = 100; int dp[2][w_max + 1], w[maxn], v[maxn], n, ans; int main() { cin >> n; for (int i = 1; i <= n; i++) cin >> w[i] >> v[i]; for (int i = 1; i <= n; i++) { bool now = i & 1; bool prev = !now; for (int j = 1; j < w[i]; j++) dp[now][j] = dp[prev][j]; for (int j = w[i]; j <= w_max; j++) dp[now][j] = max(dp[prev][j], dp[prev][j - w[i]] + v[i]); } cout << dp[n & 1][w_max]; return 0; } ```