DSA 第十週講義臺中一中電研社

--- title: DSA 第十週講義臺中一中電研社 slideOptions: theme: sky transition: 'convex' --- <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教學長)

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.