<style> h2{ color:#8B4746; } .blue{ color:#4A919E } </style> <font color="#4A919E">DSA 第十週講義</font> === >[name= 沈奕呈、陳睿倬][time=Apr 1,2022 ] ###### tags:`DSA` `Data Structure and Algorithm` `資料結構` `演算法` `Data Structure` `Algorithm` `tcirc39th` `社課` `臺中一中電研社` [TOC] --- ## <div class="blue">電研社</div> 社網:[tcirc.tw](https://tcirc.tw) online judge:[judge.tcirc.tw](https://judge.tcirc.tw) IG:[TCIRC_39th](https://www.instagram.com/tcirc_39th) 社課點名表單:[google 表單](https://judge.tcirc.tw/ShowProblem?problemid=c053) ~~社課點名表單:[google 表單](https://reurl.cc/g0V1mQ)~~ --- ## Greedy(貪婪法) 每次都採取該問題下的最佳解,而最後的輸出就是每個子問題的最佳解總和。 通常遇到這類題型,我們要做的就是尋找題目答案的原則(規則),再不斷地依據條件計算或更改輸出。 ---- ### 練習: [Add All](https://zerojudge.tw/ShowProblem?problemid=d221) 根據題目要求,我們要相加一個數列。而每兩個數字的相加成本為其相加後的總和。例如: 3+5 = 8 --> cost: 8 我們可以觀察一下範例測資,尋找輸出最小成本的規則 ---- 解答: 因為相加後的數視為一個新的數,所以n個數固定要加n-1次,導致每次相加的兩個數越小越好(目前最小的兩個數相加) ---- #### 細節: 1. 注意輸入大小,或相加過程中是否溢位 2. 時間: 由於此題輸入量5000 --> 如何有效率地尋找最小值,並在相加後排序 ---- #### priority_queue 在寫競程時,排序有助於我們方便地對資料套用一些演算法。但同時也要注意排序所花的時間。 在這裡,每相加一次就要做排序 --> 若今天數列5000個 --> 做5000-2次排序。 此時,可以考慮STL以幫你寫好的容器且會排序,如:set、mutliset還有這裡的priority_queue(以下簡寫pq) ---- 由於pq不是greedy的重點,這裡不會講太多,可以參考下面網址 [連結1](https://www.geeksforgeeks.org/priority-queue-in-cpp-stl/) [連結2](https://www.cplusplus.com/reference/queue/priority_queue/) [連結3](https://yuihuang.com/cpp-stl-priority-queue/) * pq.push(x): 將x加進pq * pq.pop(): 將最大(小)的數字取出 * pq.top(): 檢視最大(小)的數字 * pq.size(): 回傳pq長度 * pq.empty(): 回傳有無數字 ```cpp= 宣告 priority_queue<int> pq1 // 由大排到小 priority_queue<int, vector<int>, greater<int>> pq2 // 由小排到大 ``` ---- 程式碼: ```cpp= #include <bits/stdc++.h> using namespace std; typedef long long ll; int const MaxN = 5000; int a[MaxN], N; int main() { ios::sync_with_stdio(0); // 資料有點多,加速讀取 cin.tie(0); while (1){ ll x, cost = 0; // cost可能溢位 priority_queue<ll, vector<int> , greater<int> > pq; cin >> N; if (N <= 0)break; for (int i=0;i<N;i++){ cin >> x; pq.push(x); } while (pq.size()>1){ // 取最小的兩個數字 ll x1, x2; x1 = pq.top(); pq.pop(); x2 = pq.top(); pq.pop(); x = x1+x2; cost+=x; pq.push(x);// 加完記得塞回去 } cout << cost << endl; } return 0; } ``` ---- --- ## DP dynamic programming(動態規劃),是分治法的延伸 DP的分割方法為,<font color="#ff0000">將原問題遞推成數個同性質的子問題</font>,過程中會將每個不同的子問題答案作記憶化儲存,如此一來,再次遇到相同的子問題時便可以直接套用答案,省去不必要的重複計算 所以 DP = Divide & Conquer + memoization ---- 什麼時候適合用DP? 1. 最佳子結構性質:子問題的解可以推到原本的問題的解。 2. 重疊子問題:常常需要處理相同的子問題 - 不符合第一點的話沒辦法用DP - 符合第二點的時候,記憶化儲存就能有效減少執行次數,以空間換取時間 ---- ### DP VS 分治 - <font color="#ff0000">DP:</font> DP的子問題是由原問題遞推出來的,所以常常需要處理相同的子問題 <!--原問題遞推出數個子問題--> - <font color="#ff0000">分治:</font> 分治的子問題是由大問題切割出來的,雖不大重複,但會有跨區問題 ---- ### DP要點 dp 由四大要素組成 1. 尋找遞迴式(recurrence) 2. 定義子問題(state space) 3. 狀態轉移(state transition) 4. 找到原問題的答案 ---- #### 1. 尋找遞迴式(recurrence) 找出這個問題的規律,像解數學一樣寫出遞迴關係式 ---- ex.費式數列 - 設費式數列第n項為f(n) f(n){ n=1 , f(1)=1 n=2 , f(2)=1 n>2 , f(n)=f(n-2)+f(n-1)} ---- #### 2. 定義子問題(state space) (1)在分治法中,我們需要決定切割問題的方法;在dp中,我們則需要知道會出現的子問題有那些,來決定要計算的範圍 (2)開一個陣列當答案的存放區,依據要計算的範圍決定陣列的長度、答案放的位置 ---- ex.尋找費式數列第$n$項 (1)需要計算的子問題:第一項的值、第二項的值、...、第$n$項的值 (2)開個長度為$n+1$的陣列$f$,決定把第i項的值放在 $f[i]$ ps.你也可以直接將陣列長度固定為$max_n+1$,反正題目輸入的資料量不會超過他規定的最大值$max_n$ ---- #### 3. 狀態轉移(state transition) 根據前面求出的遞迴關係式,設定基本的子問題答案,再根據實作方法設計「轉移式」的表示法 如果沒有設定基本的子問題答案,你根本沒有推移子問題的起點(或終點) ---- 將轉移式對應遞迴關係式,程式的實作方法不同,轉移式寫法就不同 ```cpp= //初始子問題答案設定(initialize) f[1]=1; f[2]=1; //轉移式(之後要根據實作方法調整轉移式的表示法) f[n]=f[n-1]+f[n-2]; ``` ---- #### 4. 找到原問題的答案 根據你定義子問題及狀態轉移的方法,推理答案會出現在陣列的哪一格 ---- 第$i$項會放在第$i$格,所以答案在陣列第$n$格 ```cpp= cout<<f[n]; ``` ---- 釐清以上四點後就可以開始實作程式碼了,實作方式分兩種 - top down 使用遞迴由「原問題」推回「基本狀態」 - bottom up 使用迴圈由「基本狀態」推至「原問題」 ---- 用top down的方式比較好思考,但用bottom up的執行時間比較短,所以建議大家先用top down寫寫看,再想要怎麼轉成bottom up --- ### [frog 1](https://atcoder.jp/contests/dp/tasks/dp_a) 1. 設f(n)為跳到第n格的最小花費 f(1)=0 f(n)=min(f(n-2)+h[n-2]與h[n]的高度差 , f(n-1)+h[n-1]與h[n]的高度差) 2. 需計算跳到第1~n塊石頭的花費 `int c[n+1];` 第n格放f(n)的值 4.答案為c[n] ---- ### top down top down 是先問原問題的答案,為了尋求原問題的答案,使用遞迴回推其子問題的答案,當所有衍生出的子問題都推至「基本狀態」後,便能得解 ---- 3. 轉移式設計為 `return c[n]=遞迴式 ;` ```cpp= c[1]=0; int t1=topdown(n-1)+abs(h[n]-h[n-1]);//f(n-1)+樓差 int t2=topdown(n-2)+abs(h[n]-h[n-2]);//f(n-2)+樓差 return c[n]=min(t1,t2); ``` ---- ```cpp= #include <bits/stdc++.h> using namespace std; int n; const int max_n=1e5+1; const int max_v=1e4; const int inf=1<<30;//不會落在答案範圍內 int h[max_n]; int c[max_n]; int topdown(int n){ //終止條件:起點<=第0塊石頭,不可能發生 //所以去掉這個選項->給出一個比所有可能答案都高的值 if(n<1) return inf; if(c[n]==inf){//3.轉移式 int t1=topdown(n-1)+abs(h[n]-h[n-1]);//f(n-1)+樓差 int t2=topdown(n-2)+abs(h[n]-h[n-2]);//f(n-2)+樓差 return c[n]=min(t1,t2);//記得return的時候要記憶化 } return c[n];//算過的子問題的值不會是inf,直接套答案 } int main() { for(int i=1;i<=n;i+=1){ cin>>h[i]; c[i]=inf; } c[1]=0;//基本的子問題答案 cout<<topdown(n)<<'\n'; } return 0; } ``` ---- ### bottom up bottom up 藉由基本的子問題答案,使用for迴圈一步步組合成母問題的答案,當組合出原問題的答案,便能得解 ---- 3. 轉移式設計為 `c[n]=遞迴式 ;` ```cpp= c[1]=0; int t1=c[i-1]+abs(h[i]-h[i-1]); int t2=c[i-2]+abs(h[i]-h[i-2]); c[i]=min(t1,t2); ``` ---- ```cpp= #include <bits/stdc++.h> using namespace std; int n; const int max_n=1e5+1; const int max_v=1e4; const int inf=1<<30;//不會落在答案範圍內 int h[max_n]; int c[max_n]; int main() { for(int i=1;i<=n;i+=1){ cin>>h[i]; } c[1]=0; c[2]=abs(h[2]-h[1]); for(int i=3;i<=n;i+=1){ int t1=c[i-1]+abs(h[i]-h[i-1]); int t2=c[i-2]+abs(h[i]-h[i-2]); c[i]=min(t1,t2); } cout<<c[n]<<'\n'; return 0; } ``` --- ### 背包問題 是DP裡的經典問題。大致上的敘述: 今天有一堆物品,每個物品有各自的價值和重量。所求: 在有重量限制的狀況下選擇物品的價值總和越高越好。 背包問題實際上有兩種,一個是物品可以分割,另一種是不行,就是說只能選或不選。前者可以特過前面講的greedy寫,計算價值/重量的比例,優先選擇比值較高的。 而DP在處理的是後者,又稱 0 1背包問題,是道非常經典的題目。下面我們拿個例題來做示範。 --- #### 例題: [搬家規劃問題](https://zerojudge.tw/ShowProblem?problemid=c147) 我們就來把DP的四大重點套進這個題目吧。先想子問題,由於每個重量有不同的組合方式,所以無法從重量拆問題。所以試試看能不能由物品下手。我們可以從一種物品開始擺。擺完後,再看另外一種物品,若物品有更好的選擇或組合,那就選最大的。 ---- 看起來這方式行得通。但要如何尋找每個狀態下的最佳解呢? 這時,我們可以連同其他重量的選擇也找好。 雖然我們無法從上個重量的答案推知下個重量的答案。 但是,藉由記錄每個重量,當前w的最佳解可以變成物品價值加上$W_{重量差值}$的最佳解,省去直接窮舉的時間。 ---- weight: 1 2 value: 1 3 W: 5 || 0 | 1 | 2 | 3|4|5| |-| - | - | - | - |-|-| |1| 0 |1 |1|1|1|1| |2|0|1|3|4(3+W[1])|4|4| ---- 遞迴式: 這裡區分一下: 物品價值$v_i$, $w_i$ 每個重量最佳解$a_w$ $a_w$ = $max(a_w, v_i+a_{w-w_{i}})$ 狀態轉移: 每當有新物品進來時,掃過陣列一遍,對每個重量最佳解進行更新。但還需要另一個陣列紀錄原陣列答案。 ---- ```cpp= #include <bits/stdc++.h> using namespace std; int const MaxW = 1e6; vector<pair<int, int>> vec; int N, W; int arr[2][MaxW+1]; int ans = 0; bool cmp(pair<int, int> a, pair<int, int> b){ if (a.first != b.first) return (a.first < b.first); else return (a.second < b.second); } int main(){ stringstream ss1, ss2; string s1,s2; getline(cin, s1); ss1 << s1; string x; int idx = 0, a; int nowi = 0, nxti = 1; while (ss1 >> x){ a = stoi(x); vec.push_back({a, 0}); } getline(cin, s2); ss2 << s2; while (ss2 >> x){ a = stoi(x); vec[idx++].second = a; } cin >> W; N = vec.size(); sort(vec.begin(), vec.end(), cmp); //for (int i=0;i<N;i++){ // cout << vec[i].first << ' ' << vec[i].second << endl; //} memset(arr, 0, sizeof(arr)); for (int n=0;n<N;n++){ for (int w = 1;w<=W;w++){ if (vec[n].first > w)continue; arr[nxti][w] = max(arr[nowi][w], arr[nowi][w - vec[n].first]+vec[n].second); } swap(nowi, nxti); } cout << arr[nowi][W] << endl; return 0; } ``` --- ### 練習題 DP的題目到處都是... [AtCoder DP Contest](https://atcoder.jp/contests/dp):Atcoder上的一系列DP題,從簡單到困難都有,解完應該靈力會提升50%(? [AP325](https://judge.tcirc.tw/Problems?page=4&&tabid=AP325):第六章整章都是DP,開心解ㄅ\~大部分都不會太難,~~裡面似乎混了幾題有點可怕的東東~~ (解得一點都不開心:sob: by教學長)
{"title":"DSA 第十週講義 臺中一中電研社","slideOptions":{"theme":"sky","transition":"convex"}}
    298 views
   owned this note