## 背包們 作者：reset007 --- ## 回顧一下 DP的步驟是... ---- > 定義一個「狀態」 ->觀察題目敘述 找出狀態轉移過程 ->從頭推得答案/從尾逆推答案 --- ## 怎樣的題目算是背包問題? ---- ### 以經典形式來說 - 一個有容量限制的背包 - 有許多物品可以放進背包 - 物品有各自的體積及價值 - 最大化背包內物品的總價值 ---- ### 小提醒-關於「重量」 這個詞可能會在不同的題目中 代替「容量」或是「價值」出現 大家要小心讀題! --- ## 先來看看幾個例子 ---- ## 分數背包 ---- ### 定義 就是可以取分數個物品的背包 例如:半塊蛋糕、半台鋼琴、半張鈔票... ---- ### 想法 優先放CP值最高的 貪婪就能做了 複雜度$O(N)$ ---- ## 01背包 ---- ### 定義 對於每個物品 要嘛拿 要嘛不拿 ---- ### 想法1 窮舉物品的子集! 複雜度$O(2^N)$ (其實是$N2^N$，因為還要計算子集的重量) 慢到爆 ---- ### 想法2 對CP值做貪婪! 但是會爛掉 ---- ### 一個爛掉的case 容量限制10 有3個物品 A. 容量6 價值9 B. 容量5 價值6 C. 容量5 價值4 --- ## 小結 上述方法都不太可行 但既然背包狀況很適合當「狀態」 不妨試試DP吧 --- ## 01背包實作 下面會用DP來做這題 ---- [[CSES1158] Book Shop](https://cses.fi/problemset/task/1158)  ---- 哪個是「容量」? 哪個是「價值」? ---- ### 定義狀態 有什麼狀態可以給我們選呢? ---- ### 定義狀態 dp[**當前物品的總容量**] 好像不太方便 改一下 ---- ### 定義狀態 dp[當前**剩餘容量**] 1個狀態夠嗎? ---- ### 定義狀態 dp[當前剩餘容量][**當前考慮物品**]=最大價值 多一個比較方便 ---- ### 轉移式 「放或不放」是這裡的關鍵 ---- ### 轉移式  圖源:演算法筆記 Knapsack Problems ---- ### 轉移式 $dp[V][i]=???(dp[V][i-1], dp[V-V_i][i-1])$ ---- ### 轉移式 $dp[V][i]=max(dp[V][i-1], dp[V-V_i][i-1]+value_i)$ ---- ### 轉移式的邊界條件 - 剩餘容量夠不夠放? - 物品編號不存在? ---- ### code ```cpp= int V[n];//物品所占容量 int value[n];//物品價值 int dp[背包最大容量+1][物品種類數+1];//動態規劃每個狀態的最大價值 int solve(int v, int i){//v=剩餘容量 i=目前考慮的物品編號 if(dp[v][i])return dp[v][i];//記憶化 if(v<0)return 容量不夠不能放;//想想看 要回傳什麼才對 if(i==0)return dp[v][i]=0;//第0個物品就是不放任何東西 return dp[v][i]=max( solve(v, i-1) , solve(v-V[i], i-1)+value[i]); //遞迴轉移式 } ``` --- ### 改善一下 --- ### code ```cpp= int V[n];//物品所占容量 int value[n];//物品價值 int dp[背包最大容量+1][物品種類數+1];//動態規劃每個狀態的最大價值 void solve(int v, int n){//v=剩餘容量 n=目前考慮的物品編號 for(int i=0;i<n;i++){//窮舉n之前的每個物品狀況 for(int j=0;j<v;j++){//窮舉所有剩餘容量 if(j+) } } } ``` --- ## 常見應用 嘗試用遞迴寫出這些題目! --- ## 求最大公因數 [A005 GCD的求解](http://mdcpp.mingdao.edu.tw/problem/A005) ---- ### 遞迴關係式 $\gcd(a, b)=\gcd(a \% b, b)$ 這東西就是我們國中學到的 **輾轉相除法** ----  ---- 想想看怎麼用遞迴實作ㄅ ---- code: ```cpp= int gcd(int a, int b){ if(a < b)return gcd(b, a);//先大後小 方便我們處理 if(b == 0)return a;//若有一方整除 代表另一個數即為所求 return gcd(b, a % b);//遞迴式 } ``` --- ## 碎形 [B003 分形練習](http://mdcpp.mingdao.edu.tw/problem/B003) ---- 先放個~~萊洛三角形~~謝爾賓斯基三角形給大家看 ----  ---- 圖太大了我懶得縮orz ---- ### 遞迴關係 小物件用某個規律組成中物件 中物件再用一樣的規律組成大物件 ---- 想想看怎麼用遞迴實作ㄅ ---- 虛擬code(編譯不會過): ```cpp= bool c[2500][2500];//陣列有可能太小 n太大時需要用別的方法處理 void draw(int level, int x, int y){ if(level == 1)c[x][y]=1;//把需要輸出X的位置標註起來 int length = pow(3, level-2); draw(level-1, x, y);//左上角 draw(level-1, x+length*2, y);//右上角 draw(level-1, x+length, y+length);//中間 draw(level-1, x, y+length*2);//左下角 draw(level-1, x+length*2, y+length*2);//右下角 } int main(){ ... draw(n, 0, 0);//從左上開始 for c://輸出答案 記得該換行要換 if(c[i][j] == 1)cout<<"X"; else cout<<" "; cout<<"---"; } ``` --- ## 進階應用 遞迴還可以用在哪? ---- - 暴力搜索(枚舉 aka 窮舉) - 圖的遍歷(DFS / BFS) - 動態規劃 aka DP - ...很多很多地方 ---- 先把基本功練熟吧 這樣未來遇到也會更得心應手! --- ## 回家功課 ---- 在MDjudge右邊的Tags點擊「遞迴」 ----  --- ## 謝謝大家