###### tags: `MDCPP講義` # 動態規劃講義 **Author : 謝侑哲** --- ## 動態規劃是什麼? ---- 動態規劃，英文叫 Dynamic Programming 簡稱DP。 這兩個詞分別是 動態的 以及 規劃 就是很直接的翻譯 ---- 不過就算翻譯得很直接 正常人應該都看不懂這甚麼鬼吧 ---- 簡單來說 他就是一個把大問題拆成小問題的東西 並且可以透過合併小問題 以獲得大問題的答案 ---- 而最簡單的例子就是你們都會的費氏數列 $F_n = F_{n-1} + F_{n-2}$ 利用後面兩個子問題的答案 我們可以直接算出現在要求的問題的答案 ---- 補個，費氏數列  ---- 這時候就要來講到DP的精隨了 <記憶化> ---- 在我們講利用遞迴計算$F_n$需要從頭找到尾 ```cpp= int fibo(int n){ if(n == 0) return 1; if(n == 1) return 1; return fibo(n - 1) + fibo(n - 2); } ``` 的確這是一個方法 但你們會發現你們寫的code都比這好很多 因為這是一個很暴力也很慢的方法 ----  他的運算會是這張圖所表示的 想想你們直接迴圈寫這個 要算第N個數字也只需要計算N次對吧 那為甚麼要把它拆成兩個問題寫呢? ----  仔細觀察，會發現他重複計算了很多一樣的東西 那這就是DP的精隨 記憶化 該出場的時候了 ---- ## 記憶化? ---- DP這個詞是在1950年代被提出的 而他最重要的記憶化概念 老蔣早在1940年代就提出來了，就是 ### 空間換取時間  ---- 也就是我們可以把我們所得到的小問題的答案都記錄下來，當我們需要再用到，就可以直接拿出來用，不需要再重新計算一遍  這樣就算了5次 ---- 可以把code寫成以下樣子 ```cpp= int dp[MAXN]; int fibo(int n){ if(n <= 1) return 1; if(dp[n]) return dp[n]; return dp[n] = fibo(n - 1) + fibo(n - 2); } ``` 利用陣列來儲存答案 消耗陣列需要付出的記憶體，換來更快的時間 ---- 時間複雜度從O($2^N$)直接變成O(N)  ---- 所以 DP 簡單來說 就是透過一堆好算小問題的堆疊以及紀錄 來算出那些麻煩的東西 --- ## DP能幹嘛? ---- 因為他可以由小問題推到大問題的特性 他同常被應用在兩種問題上 1. 最優子結構問題 2. 重疊子問題 ---- 最優子結構問題 利用小問題的最佳解，來推知大問題的最佳解 ---- 重疊子問題 處理問題合併的時候，會重複用到小問題的答案 像是費氏數列就是一種重疊子問題 ---- 另外動態規劃也有非常多種的種類 ---- 1. 線性DP 2. 區間DP 3. 環形DP 4. 樹上DP 5. 圖上DP 6. 背包DP 7. 狀壓DP ... ---- 因為DP本身需要解出許多問題的暴力特性 他也有不少的優化方式 --- ## DP的不同寫法 ---- DP有著top-down、bottom-up 兩種不同的寫法 差別大概就在於利用遞迴或迴圈寫 ---- top-down 利用遞迴來寫動態規劃 從上找到他的子問題，再計算子問題 通常這種方式會比較直觀 ```cpp= int dp[MAXN]; int fibo(int n){ if(n <= 1) return 1; if(dp[n]) return dp[n]; return dp[n] = fibo(n - 1) + fibo(n - 2); } ``` 就像這樣，可以輕易地看出他在幹嘛 ---- bottom-up 利用迴圈的方式推答案 直接從子問題堆向大問題的答案 用費氏數列就像這樣 ```cpp= int dp[MAXN]; dp[0] = dp[1] = 1; for(int i = 2; i <= n; i ++){ dp[i] = dp[i - 1] + dp[i - 2]; } ``` 通常他看起來會比較不直觀 因為比較需要去思考它的迴圈順序對DP的影響 當我們倒轉迴圈時也可能影響到整個DP的做法、空間、時間 ---- 這樣看起來感覺用遞迴的top-down比較好寫對吧 但我們通常會比較推崇用bottom-up的方式 ---- top-down用的遞迴本質上是stack 比起迴圈，運作起來要花更多時間 這在你們學習遞迴時應該就有說到了 還有剛剛講到他是由上往下推，再推回上面 所以花的時間又更多了 ---- 另外，剛剛有說到迴圈的順序是有可能影響到DP的 但同樣的我們也可以利用這個特性 改變DP的順序，來達到一些遞迴很難實現的效果 ---- 舉個栗子 ```cpp= for (int i = 0; i < n; ++i) for (int j = w[i]; j <= wmx; ++j) c[i+1][j] = max(c[i][j],c[i][j-w[i]] + cost[i]); ``` ```cpp= for (int i = 0; i < n; ++i) for (int j = wmx; j >= w[i]; --j) c[j] = max(c[j], c[j - w[i]] + cost[i]); ``` 這是你們之後會學的背包DP 上下兩個code其實是一樣的東西 但下面的只是倒轉for順序，就直接簡化掉一個維度的陣列 --- ## DP基本概念 ---- DP最重要的兩個東西 1. 狀態 2. 轉移 ---- 狀態 就是我們描述某個子問題的方法 通常會是利用子問題的重要特性 同樣以費氏數列來說 ```cpp= int dp[MAXN]; dp[0] = dp[1] = 1; for(int i = 2; i <= n; i ++){ dp[i] = dp[i - 1] + dp[i - 2]; } ``` 陣列的指標就是他的狀態 因為它代表了那是第N個數字的答案 第幾位也是費氏數列中最重要的特性 ---- 轉移 就是我們把小問題合併成大問題的過程 再拿一次費式數列 ```cpp= int dp[MAXN]; dp[0] = dp[1] = 1; for(int i = 2; i <= n; i ++){ dp[i] = dp[i - 1] + dp[i - 2]; } ``` $dp[i] = dp[i - 1] + dp[i - 2];$ 這句就是他的轉移式 ---- 另外還有一個東西我們稱為決策 簡單來講就是判斷使用甚麼樣的轉移的方法 決策的集合我們又稱為策略 阿這之後再提 ---- 關於狀態及轉移的思考? ---- 狀態的思考 我們通常會根據題目的性質 去思考影響答案推算的關鍵特性 另外我們再思考完狀態後 如果想不出轉移式，那也可能是想錯東西 可以換個狀態想想看 ---- 轉移的思考 這是DP最關鍵的地方，通常思考的方式 是去想小問題跟大問題之間的關係 並且有一個很重要的點 要先相信自己的小問題答案正確 先得出轉移式 再去解決其他小問題的限制 ---- 看到這裡一定一堆人不知道我在工三小 所以我們直接進題目看看ㄅ --- ## 線性DP ---- 我等等在來講甚麼是線性DP ---- 入門題 [爬樓梯問題](http://mdcpp.mingdao.edu.tw/problem/A048) ---- 讓我們先來分析他的狀態及轉移式吧 ---- 首先這種樓梯問題跟費式數列其實長得頗像 他除了第幾階之外，大概也沒有其他特性了 所以她的狀態就訂為 樓題的階數 ---- 他的轉移式 因為我們要求第N階的樓梯 那麼樓梯有一個特性是要由下往上走，他又剛好只有兩種走法 那麼我們就可以輕易知道他可能從哪階上來 ---- 因為只能走1或2階 所以N的子問題應該是N-1跟N+1 至此就可以輕鬆推出轉移式 $dp(N) = dp(N-1)+dp(N-2)$ 兩種可能性相加就是答案 其實就是費式數列啦，所以我就不附code了 ---- [爬樓梯問題之二](http://mdcpp.mingdao.edu.tw/problem/A049) ---- 插播 : 取模 就是取餘數的意思 以下列方法表示 $7 \equiv 1(\mod 3)$ 就是7除以3等於1的意思 ---- 簡單來說就是第一題 只是加了個不能走的障礙 ---- 所以她的基本狀態跟轉移式是一樣的 但他就是多了一個限制阿，哪要怎麼處理? ---- 記得剛剛講哦決策嗎? - 判斷使用甚麼樣的轉移的方法 也就是說一個DP可以不只有一種轉移式 ---- 那當我們遇上轉移壞掉的樓梯時要怎麼辦呢? 很直觀的就是不要加上去嘛 那就可以簡單寫成下面的樣子 ```cpp= int no[1000050]; // 儲存誰壞掉了 int dp[1000050]; for(int i=2;i<=n;i++){ if(!no[i-1]) dp[i] += dp[i-1]; if(!no[i-2]) dp[i] += dp[i-2]; } ``` ---- 不過上面的方法是有點麻煩啦 所以我們其實可以在遇到壞掉的樓梯時 直接continue，這樣就可以讓他保持0 就算被加到也沒差 ---- 範例code ```cpp= const int mod = 1e9 + 7; int dp[1000005]; bool no[1000005]; signed main(){ int n, k; cin >> n >> k; for(int i = 1; i <= k; i ++){ int a; cin >> a; no[a] = 1; } dp[0] = dp[1] = 1LL; for(int i = 2; i <= n; i ++){ if(no[i]) continue; dp[i] = (dp[i - 1] + dp[i - 2]) % mod; } cout << dp[n] << endl; } ``` ---- 現在讓我們回頭講甚麼是線性DP ---- 線性DP就是轉移的方式像一條線一樣 由前往後，一路推過去  是最簡單的DP ---- 其他不同的DP分類也有不同的做法 有些是因為狀態需要特殊處理 有些是需要特殊的轉移 ---- 然後再來一題練習吧 [爬樓梯問題之三](http://mdcpp.mingdao.edu.tw/problem/A050) --- 線性DP之二 ---- 剛剛看過一維的DP，讓我們來看看多維的吧 ---- [採果實問題](http://mdcpp.mingdao.edu.tw/problem/A052) 他是多維的，但也是線性DP喔 ---- 來分析他的狀態跟轉移ㄅ ---- 狀態 能從題目裡得知的資訊有 x座標 y座標 果實數量 果實數量很顯然是我們要求的東西 那麼 x座標 y座標 哪個會是我們的狀態呢 顯然兩個都是，那我們可以開二維陣列儲存他 $dp[x][y]$ 裡面的值就應該是到那格可以得到的果實最大值 ---- 轉移式 這題有點像走樓梯的變體 一樣的概念，樓梯只能由下往上走 果實也只能由左上到右下採 因為它可以從左邊或上面拿，但一次只能選一個拿 所以在二擇一下，我們只能選最大的那個 轉移式應該是 $d[i][j] = max(dp[i-1][j],dp[i][j-1])+arr[i][j]$ 而$arr[i][j]$是那一格的果實數量 ---- 範例code ```cpp= #include<bits/stdc++.h> using namespace std; int dp[1005][1005], a[1005][1005]; int main(){ int n; cin >> n; for(int i = 1; i <= n; i ++){ for(int j = 1; j <= n; j ++){ cin >> a[i][j]; } } for(int i = 1; i <= n; i ++){ for(int j = 1; j <= n; j ++){ dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + a[i][j]; } } cout << dp[n][n] << "\n"; } ``` --- 線性動態規劃之三 ---- 再來要講一個經典的DP用法 ## LCS(最長公共子序列) ---- [LCS](http://mdcpp.mingdao.edu.tw/contest/19/problem/T015) ---- 何謂LCS(最長公共子序列)呢? ---- 首先子序列就是從一個序列中 抓任意數字出來組成的序列 5 8 4 2 7 3 6 5 3 就有一個子序列是 8 7 6 3 ---- LCS簡單來講，就是找兩個序列中 一樣的子序列中，最長的 ---- 2 **5** 7 9 **3** 1 **2** 3 **5** **3** **2** 8 的LCS就是 5 3 2 ---- 至於要怎麼做呢，同樣來分析狀態跟轉移吧 ---- 狀態 我們擁有 第一序列的位置 第二序列的位置 第一序列的值 第二序列的值 很顯然值是我們用來推答案的東西 那兩個子序列的位置就應該是我們的狀態了 $dp[i][j]$ i是第一子序列的位置 j是第二子序列的位置 ---- 轉移式，LCS的轉移式其實並沒有很直觀 首先我們要先想在$dp[i][j]$之間有甚麼樣的關係 這裡我們假設兩個子序列叫做sub1,sub2 末端元素叫做e1,e2也就是在i,j的位置的值 會發現他有3種變化關係 ---- 1. 當e1==e2時 $dp[i][j]$會是$dp[i-1][j-1]+1$ ---- 2. 當e1!=e2時，會有兩種情況 $dp[i][j]$跟$dp[i-1][j]$或$dp[i][j-1]$一樣長 但不會跟$dp[i-1][j-1]$一樣長 因為當兩者不一樣時 任一都還有可能跟另外一個序列的前面數一樣 但不會同時跟前面數一樣，因為這樣就交叉了  ---- 所以要求最大值的話 我們的決策是e1是否等於e2 轉移式分別是 $dp[i][j]=dp[i-1][j-1]+1$ $dp[i][j]=max(dp[i-1][j],dp[i][j-1])$ ---- LCS模板 ```cpp= int LCS() { // 當s1或s2是空的，則LCS長度0。 for (int i=0; i<=N1; i++) length[i][0] = 0; for (int j=0; j<=N2; j++) length[0][j] = 0; for (int i=1; i<=N1; i++) for (int j=1; j<=N2; j++) if (s1[i] == s2[j]) length[i][j] = length[i-1][j-1] + 1; else length[i][j] = max(length[i-1][j], length[i][j-1]); return length[N1][N2]; } ``` ---- 習題: [ZJ 大耳神下麵真好吃](https://zerojudge.tw/ShowProblem?problemid=c499) --- 第一堂課的尾聲 ---- 我準備了一些線性DP題目 我覺得算有難度，但又不會到解不出來 這些題目還沒被搬上MDjudge 畢竟搬這些也是個工程 所以需要你們先在外部網站寫了 ---- [凱薩軍團](https://codeforces.com/problemset/problem/118/D) 這題是codeforce上的題目，所以要自己辦帳號 因為是俄羅斯的網站，所以是全英文的，可能會看得有點吃力 如果看不懂題目可以問一下講師喔 ---- [大師](https://www.luogu.com.cn/problem/P4933) 這題是洛谷上的題目，也要自己辦帳號 阿是中國的網站，是簡體中文的，我想大家應該都能看懂 但如果對中國有點敏感的話，那就要等我們搬上MDjudge了 順帶一提，這提頗有難度，你們解起來會很吃力喔 ---- 至於這幾題如果課程來得及 我考慮在下次上課講解 --- 第二次上課 --- ## 區間DP ---- 跟線性DP比起來 區間DP的性質差異在於 它的狀態不會像爬樓梯 陣列一維代表一個性質 而是利用兩個以上的點 表示一個區間 $like \ this:$ $dp[i][j] = 區間i - j$ ---- **$dp[1][5]$**  **$dp[2][6]$**  ---- DP這東西還是要看例題比較好懂呢 ---- [史萊姆](https://atcoder.jp/contests/dp/tasks/dp_n) ---- 給你一排史萊姆 進行合併操作 假設兩個連續史萊姆分別大小為x,y 每次合併需要花費x+y元 目標要使他合到剩一隻 並且使花費最少 ---- 概念: 我們可以確定合併費用的長度只有兩個史萊姆 當我們要合併三隻史萊姆時 會有三種情況: ----  $cost = 24$ ----  $cost = 28$ ---- 我們觀察可以發現他最後合併出來的東西都會一樣 那麼既然合併出來的東西沒差 那我們自然應該挑選花費最少的第一個 但問題是我們要怎麼知道怎麼找到最小的那個 ---- 這時候就是DP該出場的時候了 ---- 仔細觀察，會發現 每個合併都是由兩個區間合起來的 第一張是由(1,2)+(3,3)的區間組成的 第二張是由(1,1)+(2,3)的區間組成的 而一開始我們已知的值是所有長度1、2的區間 那我們就可以利用1、2的區間推出3的區間 進而推出4、5、6...的區間 ---- 現在可以推知她的狀態 要表示一個區間最簡單的方法 標示出他的左端點跟右端點 $dp[i][j]$ ---- 看到上面照順序推1,2,3,4,5... 很直覺的就會想到for迴圈枚舉區間長度把 接著可以再用一次for迴圈 以每個點作為區間的左端點枚舉所有區間 ---- 他的轉移會長得像一下這樣 ```cpp= for(int k=1;k<n;k++) // 從區間2開始(1+1) 到區間N(1+N-1) for(int i=1;i<=n-k;i++) for(int j=i;j<=i+k;j++){ dp[i][i+k] = min(dp[i][i+k] , dp[i][j] + dp[j+1][i+k] + pre[i+k] - pre[i]); } ``` ---- 在解決狀態跟轉移之後 剩下初始化跟邊界限制了 ---- 初始化的話，因為我們要取最小值 所以可以全部初始化成超大 然後邊界條件基本上在for迴圈裡就處理好了 所以可以直接忽略 ---- 參考code ---- ```cpp= #include <bits/stdc++.h> #define int long long using namespace std; int dp[500][500]; int pre[500]; signed main() { memset(dp,0x3f,sizeof(dp)); int n,x; cin>>n; for(int b=1;b<=n;b++) cin>>x,pre[b]=pre[b-1]+x,dp[b][b]=0; for(int le=2;le<=n;le++) { for(int c=1;c<=n-le+1;c++) { int l=c,r=c+le-1; for(int m=l;m<r;m++) { dp[l][r]=min(dp[l][r],dp[l][m]+dp[m+1][r]+pre[r]-pre[l-1]); } } } cout<<dp[1][n]; } ``` ---- 類似題: [切木頭](https://zerojudge.tw/ShowProblem?problemid=d686) ---- 阿區間DP題目有點難找 所以先跳過，之後講環形DP的時候再來繼續 --- ## 背包DP ---- 背包DP在程式競賽裡 算是非常重要的DP (跟區間DP比起來) ---- 不過背包DP的題目乍看之下其實不太像DP 秀一題給你們看 ---- explosionn 有 $N$ 隻蘿莉 每隻蘿莉的體積為$X_i$ 他對每隻蘿莉的喜愛度為$w_i$ 今天他要帶著他的蘿莉們出去玩 但是他的車子空間有限，只能載體積$M$的蘿莉 請問要載那些蘿莉出去玩 才能讓他感到最開心(喜愛值加總最多) ---- 這題目看起來完全就不像DP吧 但是她事實上是可以利用DP的方法來做了 ---- 先稍微講一下背包問題的概念 背包事實上指的是一個容器 背包問題通常是在你有各種不同物品時 物品有其體積及價值 要怎麼在有限容量的背包裏面 放進最高價值且符合條件的物品 ---- 以剛剛在蘿莉出遊的問題為例 車子容量就是背包容量 蘿莉就是物品 蘿莉體積就是物品體積 蘿莉的喜愛值就是物品價值 ---- 而背包DP主要又分成 1. 01背包問題 2. 無限背包問題 3. 有限背包問題 當然還有更多分支，不過今天主講這幾種 --- ## 01背包問題 ---- 01背包問題顧名思義 就是每種物品只能放進0個或一個 相當於放或不放 ---- 這裡我舉個題目 ---- 桌上有一個耐重1000g的背包 一旁放著四個物品，分別是 🎂蛋糕 850g 400$ 🍊橘子 300g 150$ 🍌香蕉 500g 150$ 🍞吐司 200g 120$ 試問怎麼樣可以在背包中裝入最高價值的東西? ---- 因為物品很少，所以我們可以一眼就看出 放入🍊🍌🍞的總價值是最高的 這樣總共是1000g 420$ ---- 那麼如果在程式中要怎麼找出最佳解呢 ---- 首先我們一般想到最值觀的方法就是 枚舉每個物品放或不放 這樣的時間複雜度是$O(2^N)$ 很顯然是個爛作法 只要放30物品就爆了 ---- 所以我們需要用到DP來解決問題 ---- 首先來分析可以從題目中獲取甚麼資訊 ---- >-耐重1000g的背包- 得知背包容量 >-🎂蛋糕 850g 400$- 得知物品重量、價值 >-在背包中裝入最高價值的東西?- 得知目標 ---- 我們能從題目知道的特性有 背包容量、物品重量、價值 那麼顯然價值會是我們所追求的東西 所以她應該是我們的記憶化要記錄的東西 而不是我們的狀態 剩下的背包容量、物品重量就有可能成為狀態 ---- 現在我們來針對這兩個性質進行分析 ---- 物品重量要作為不同的問題 那我們能想到的就是把物品重量作為狀態 但是要轉移他卻是我們想不到的 因為不同物品之間是不存在互相影響的關係的 就算要把每個物品重量的值合在一起 轉移式也很難構造出來 因此我們斷定物品重量不會是他的狀態 ---- 至於背包容量 將其作為問題是合理的 並且可以大概想到他的轉移式 由多個小容量的袋子是可以推知大容量袋子的數值的 $dp[i] = dp[j]+dp[k]$ 容量i的袋子可以裝入容量j價值+容量k價值 同時後面容量為k的背包我們可以直接換成 重量為k的物品計算,因為$j+k=i$,$j=i-k$ 變成$dp[i] = dp[i-k]+重量k的物品價值$ ---- 剛剛講到我們可以從小容量的背包推到大容量的背包 所以一般來窩我們會用一個for迴圈來枚舉1~N容量的背包 從小到大，慢慢算出子問題，再合併成大問題 ---- 另外我們為了要準確把問題的答案堆出來 我們的for迴圈會利用物品順序一個個考慮進來 在考慮完之後就丟棄，不讓她影響 至於兩個for迴圈怎麼排，就看下面的code吧 ---- 01背包問題模板 ```cpp= // cost陣列存物品價值 c陣列存DP記憶的東西 weight陣列存物品重量 void knapsack(int n, int w) { memset(c, 0, sizeof(c)); for (int i = 0; i < n; ++i) // 窮舉每種物品 for (int j = 0; j <= w; ++j)// 窮舉每種重量 if (j - weight[i] < 0) // 耐重能力不足，故只能不放。 c[i+1][j] = c[i][j]; //前面代表枚舉物品到第i個，後面代表容量 //枚舉存入第幾個物品是為了防止重複計算 else // 耐重能力足夠，可以放或不放。 c[i+1][j] = max( c[i][j], c[i][j - weight[i]] + cost[i] //依照大選擇放或不放 //所以可以看出背包問題實際上是最優子結構問題 ); cout << "最高的價值為" << c[n][w]; } ``` 時間複雜度O(NW) ---- 記錄存入第幾個物品是為了防止重複計算? 因為我們的迴圈是由小到大跑的 所以在我們的紀錄中，我們會先更新小容量 如果沒有紀錄目前在存第幾個物品會遇到以下問題 ---- 設物品A 10g 20$ $dp[10] = dp[0]+20$ (放入一個物品A) $dp[20] = dp[10]+20$ (再次放入物品A) 可以發現只有一個的物品被放了兩次，造成重複計算的問題 ---- 加上枚舉到第i個 設物品A 10g 20$，且為第3個物品 $dp[10][3] = dp[0][2]+20$ (放入一個物品A) $dp[20][3] = dp[10][2]+20$ (再次放入物品A) 發現更新記憶體時只會從前一個物品的數據更新 使得物品不會被重複計算 ---- 讓我們利用一開始的例子來實際運作一遍吧 ---- 第一次迴圈 對(🎂蛋糕 850g 400$)進行枚舉 ```cpp= dp[0][1] = dp[0][0]... dp[849][1] = dp[849][0]; //容量不足 dp[850][1] = dp[0][0]+400... dp[1000][1] = dp[250][0]+400;//容量足 dp[0~849] = 0,dp[850~1000][1] = 400; ``` ---- 第二次迴圈 對(🍊橘子 300g 150$)進行枚舉 ```cpp= dp[0][2] = dp[0][1]... dp[299][2] = dp[299][1]; //重量不足 dp[300][2] = dp[0][1]+150... dp[849][2] = dp[549][1]+150; //重量足夠放橘子 dp[850][2] = dp[850][1]... dp[1000][2] = dp[1000][1]; //不放橘子放蛋糕比較划算 //$dp[850~1000][1] > dp[550~700][1]+150$ dp[0~299][2] = 0,dp[300~849][2] = 150,dp[850~1000][2] = 400; ``` ---- 後面兩圈以此類推 ```cpp= 🎂蛋糕 850g 400$ 🍊橘子 300g 150$ //註解後面對應當時放了甚麼 考慮放🍌香蕉 500g 150$ dp[0~299][3] = 0,dp[300~799][3] = 150;//0,🍊 dp[800~849][3] = 300,dp[850~1000][3] = 400;//🍊🍌,🎂 考慮放🍞吐司 200g 120$ dp[0~199][3] = 0,dp[200~299][3] = 120;//0,🍞 dp[300~499] = 150,dp[500~800] = 270;//🍊,🍊🍞 dp[800~849][3] = 300,dp[850~999][3] = 400;//🍊🍌,🎂 dp[1000][3] = 420 //🍊🍌🍞 ``` 從實際的數值出來之後 應該可以感受到背包DP在幹嘛了 ---- 01背包問題弄懂之後 接下來就是更進階的背包問題了 俗話說頭過身就過 聽懂01背包相信在來也難不倒你們 --- ## 01背包問題--空間複雜度優化版 ---- 還記得我們前面講的 可以透過for迴圈的順序改變 造成不同的結果嗎(P4-8) ---- ```cpp= for (int i = 0; i < n; ++i) for (int j = w[i]; j <= wmx; ++j) c[i+1][j] = max(c[i][j],c[i][j-w[i]] + cost[i]); ``` ```cpp= for (int i = 0; i < n; ++i) for (int j = wmx; j >= w[i]; --j) c[j] = max(c[j], c[j - w[i]] + cost[i]); ``` 學完01背包之後 我們可以發現下面的寫法 省略掉了記錄到第幾個物品的那一維 ---- 當初紀錄第幾個物品時 是為了避免重複計算 但那是建立在一個先決條件 **從小到大枚舉重量** ---- 我們的背包DP是用小容量更新大容量 所以從小到大枚舉會造成小容量先更新 進而影響到大容量被重複更新 ---- 但如果我們倒著做，讓大容量先被更新 因為大容量不會影響小容量 就可以避免重複更新的問題了 ---- $like\ this:$ 設物品A 10g 20$，且為第3個物品 原來 $dp[10] = dp[0]+20$ (放入一個物品A) $dp[20] = dp[10]+20$ (再次放入物品A) 逆序 $dp[20] = dp[10]+20$ (放入一個物品A) $dp[10] = dp[0]+20$ (放入一個物品A) 會發現這次先做20 就不存在20放了兩個物品的情況了 ---- 01背包問題--空間複雜度優化版模板 ```cpp= void knapsack(int n, int w) { memset(c, 0, sizeof(c)); for (int i = 0; i < n; ++i) { int weight = weighti[i]; int cost = costi[i]; for (int j = w; j - weight >= 0; --j) c[j] = max(c[j], c[j - weight] + cost); } cout << "最高的價值為" << c[w]; } ``` ---- 習題 [ZJ 裝貨櫃問題](https://zerojudge.tw/ShowProblem?problemid=b184) --- ## 無限背包問題(完全背包問題) ---- 無限背包問題就如他的名字一樣 與"01"的差別在於"無限"這兩個字 ---- 我們知道01代表一種物品只能拿1個或0個 那麼無限背包問題就是可以拿無限個 ---- explosionn 有 $N$ 種年紀蘿莉 並且每種都有無限隻 每種蘿莉的體積為$X_i$ 他對每種蘿莉的喜愛度為$w_i$ 今天他要帶著他的蘿莉們出去玩 但是他的車子空間有限，只能載體積$M$的蘿莉 請問要載那些蘿莉出去玩 才能讓他感到最開心(喜愛值加總最多) ---- 事實上要解決這個問題非常簡單 剛剛在優化01背包問題就講過解法了 ---- 還記得我們反轉for迴圈的意義是甚麼嗎 ---- 是為了避免重複計算(14-4) ---- 那麼當我們遇到無限背包問題時 我們就是要重複計算他們 ---- 因為當一個物品可以無限拿 就代表他在有限的重量中可以一直放 所以重複計算就可以解決這問題 ---- 那我們要做得很簡單 就是把原本的for迴圈轉回來就好了 ---- 無限背包問題範例code ```cpp= void knapsack(int n, int w) { memset(c, 0, sizeof(c)); for (int i = 0; i < n; ++i) { int weight = weight[i]; int cost = costi[i]; for (int j = weight; j <= w; j++) c[j] = max(c[j], c[j - weight] + cost); } cout << "最高的價值為" << c[w]; } ``` 時間複雜度O(NW) ---- 習題: [瘋狂採藥](https://www.luogu.com.cn/problem/P1616) --- ## 有限背包問題(多重背包問題) ---- 有限背包 顧名思義重點就是有限 何謂有限? ---- 我們有好幾種物品 每個物品有不同的數量 而且是可以拿完的 ---- 以題目為例 ---- explosionn 有 $N$ 種年紀蘿莉 10歲有 5 隻,11歲有 3 隻,12歲有 2隻 剩下的太老的他不要 每種蘿莉的體積為$X_i$ 他對每種蘿莉的喜愛度為$w_i$ 今天他要帶著他的蘿莉們出去玩 但是他的車子空間有限，只能載體積$M$的蘿莉 請問要載那些蘿莉出去玩 才能讓他感到最開心(喜愛值加總最多) ---- 至於要怎麼做呢? ---- 其實我們只要沿用01背包問題的code 然後枚舉不同數量的物品就行了 ---- 因為有限背包問題要滿足的條件就是 1. 不能重複計算(不然放一個跟放兩個就變一樣了) 2. 要有不同數量的差別(利用多一層for迴圈枚舉) ---- 有限背包問題範例code ```cpp= void knapsack(int n, int w) { memset(c, 0, sizeof(c)); for (int i = 0; i < n; ++i) { int weight = weight[i]; int cost = cost[i]; int num = min(w/weight,number[i]); //w表背包容量 //number[i] 表第i種物品有幾個 // 此句用來算最多放幾個物品 for(int k=1;k<=num;k++)//枚舉放第幾個物品 for (int j = w; j - weight >= 0; --j) c[j] = max(c[j], c[j - weight] + cost); } cout << "最高的價值為" << c[w]; } ``` 時間複雜度O(NWM) ---- 這裡我們以 重量3 價值1 的物品 及容量15的背包舉例 ---- 當我們多放一層for迴圈 可以發現，我們是利用 檢測放第i個物品時放不放得下  ---- 以此圖來說 第一個物品時，都可以放得下 放到第二個物品時，容量3的空間就放不下了 ---- 不過這個時間複雜度是滿爛的吧 O(NWM)假設變數都一樣大的話 那他放個1000就爛掉了 所以我們接下來要來試著優化他 --- ## 有限背包問題--時間優化版本 ---- 這次優化我們需要用到一個特別的技巧 二進制拆分 ---- 甚麼是二進制拆分呢 就是我們可以把任一個數拆成$2^N$組成的數 例如: 20 : 10100 -> 4+16 14 : 1110 -> 2+4+8 6 : 110 -> 2+4 ---- 對於拆分後的數字 我們可以利用轉移式的改寫 ```cpp= c[j] = max(c[j], c[j - weight] + cost); ``` ```cpp= c[j] = max(c[j], c[j - weight*k] + cost*k); ``` 讓他從一項一項加 變成可以疊加不同數量的 ---- 再利用剛剛二進制拆分的特性 我們可以把物品數量變成 1、2、4、8...$2^n$、num 讓他可以剛好加乘我們要的數 ---- 再用 重量3 價值1 的物品 及容量15的背包舉例 ---- 可以發現用$2^i$剛好可以組出所有數  最後DP出來的答案會跟原來一樣 ---- 範例code ```cpp= void knapsack(int n, int w) { for (int i = 0; i < n; ++i) { int num = min(number[i], w / weight[i]); for (int k = 1; num > 0; k *= 2) { if (k > num) k = num; num -= k; for (int j = w; j >= weight[i] * k; --j) c[j] = max(c[j], c[j - weight[i] * k] + cost[i] * k); } } cout << "最高的價值為" << c[w]; } ``` ---- 習題: [TIOJ Striker的秘密](https://tioj.ck.tp.edu.tw/problems/1387) --- ## 與背包問題相關的一些有趣問題 ---- ### 湊錢問題 ---- 給定許多種不同面額的錢幣，能否湊得某個價位？ ---- 這種問題事實上是無限背包問題的變體 物品重量變成面額 背包容量變成要湊的價位 而我們的目標是湊到剛好的價位 而不是求最大值 ---- 要解這題，首先我們要預設一件事 0元是個絕對可以湊到的價格 ---- 接著開始用各種面額 看看從已經確定可以湊到的價格 湊出另外幾種價格 ---- 範例code ```cpp= void change(int m) { memset(c, 0, sizeof(c)); c[0] = 1; // 依序加入各種面額 for (int i = 0; i < n; ++i) // 由低價位逐步到高價位，就是無限背包的寫法 //如果他給的大小不一，可以先排序 for (int j = price[i]; j <= m; ++j) c[j] = (c[j]||c[j-price[i]]); //當這個價格本身可以湊到 //或是可以從其他價格湊到，都會是1 if (c[m]) cout << "湊得到"; else cout << "湊不到"; } ``` ---- 現在我們確定了這個價格可不可以湊到 那有幾種方法可以湊到呢? ---- 這其實非常好寫 因為我們前面的code是再判斷他能否被成功湊到 那我們只要記錄一個價格被誰湊到 湊到他的人有幾種方法 就可以算出他的方法數了 ---- 畫成圖會像是數學上 計算圖中到某個點的方法數  ---- code改起來也非常輕鬆 只要把 ```cpp= c[j] = (c[j]||c[j-price[i]]); ``` 改成 ```cpp= c[j] = c[j]+c[j-price[i]]; ``` 如果判斷成功，就把前面價位的方法數加上來 ---- 範例code ```cpp= void change(int m) { memset(c, 0, sizeof(c)); c[0] = 1; // 依序加入各種面額 for (int i = 0; i < n; ++i) // 由低價位逐步到高價位，就是無限背包的寫法 //如果他給的大小不一，可以先排序 for (int j = price[i]; j <= m; ++j) c[j] = c[j]+c[j-price[i]]; cout << "有" << c[m] << "種方法"; } ``` --- 第二節課的尾聲 ---- 其他還有一些有趣的相關題目 不過礙於時間關係 我猜測我講到這裡已經沒什麼時間了 所以就先不講惹 阿不知道下次還是不是我繼續講 或者有人想要繼續衝 留下一些資源給你們 [演算法筆記](https://web.ntnu.edu.tw/~algo/KnapsackProblem.html#1) [板橋高中講義](https://sites.google.com/site/pcshic/zi-xun-pei-xun) 註 : 2019基礎演算法2第二章 ---- 這裡還有兩個題單 你們可以去練練看 [Atcoder DP contest](https://atcoder.jp/contests/dp/tasks) 日本網站，但是有英文可以看，而且很直接，容易看懂 [洛谷 背包問題題單](https://www.luogu.com.cn/training/5197) 中國網站，簡體中文 這兩個題單如果刷完 你們的背包問題大概就完全精熟了吧