DP & Greedy - HackMD

# DP & Greedy 動態規劃與貪婪 By 賴昱錡 --- ## What is DP? Dynamic programming ---- ### Definition + dynamic programming = **divide-and-conquer method + memoization** ---- ![image](https://hackmd.io/_uploads/ryk_CtFSyg.png =60%x) ---- ### Implementation + top-down + bottom-up ---- ### 例子: 走樓梯有 n 個階梯，每次只能走 1 格或 2 格，試問共有幾種走法？ ---- ### Observation f(n) = + 1 , if n = 1 + 2 , if n = 2 + f(n-1) + f(n-2) , if n >= 3 and n <= 5 ---- ### Recursion ```cpp= int f(int n) { if (n == 0 || n == 1) return 1; else return f(n-1) + f(n-2); } ``` ---- ### Top-down ```cpp= int table[6]; bool solve[6]; int f(int n) { // [initial states] if (n == 0 || n == 1) return table[n] = 1; // [computation] if (solve[n]) return table[n]; table[n] = f(n-1) + f(n-2); solve[n] = true; return table[n]; } ``` ---- ### Bottom-up ```cpp= int table[6]; void dynamic_programming() { // [initial states] table[0] = 1; table[1] = 1; // [computation] for (int i=2; i<=5; i++) table[i] = table[i-1] + table[i-2]; return; } ``` ---- ### General Solution 怎麼找？ Use charateristic equation! --- ## Examples of DP ---- ### Hanoi Tower (河內塔) 過於簡單的例子，但可以複習高一數學XD ![image](https://hackmd.io/_uploads/H1bE3H2Bke.png =50%x) ---- ### Knapsack problem (0-1 背包問題) 你有一個書包，最大負重為 W，有 n 個物品，他們分別具有 $w_i$ 的重量與 $v_i$ 的價值，我最多可以裝多少價值？在這裡 0-1 是指只能拿或不拿，此類問題也有可能是 fractional 的～ ---- ### pseudo code ```pseudocode= function knapsack(weights, values, n, W): // Create a 2D table to store solutions to subproblems // dp[i][w] represents the maximum value that can be obtained // with the first i items and a knapsack capacity of w dp = array[n+1][W+1] // Initialize the table for i = 0 to n: for w = 0 to W: if i == 0 or w == 0: dp[i][w] = 0 // Fill the dp table for i = 1 to n: for w = 1 to W: if weights[i-1] <= w: // Include the item or exclude it, take the maximum dp[i][w] = max(values[i-1] + dp[i-1][w-weights[i-1]], dp[i-1][w]) else: // Exclude the item dp[i][w] = dp[i-1][w] // The maximum value for the full capacity is stored at dp[n][W] return dp[n][W] ``` ---- ### 換零錢 (1) Consider a money system consisting of $n$ coins and each coin has a positive integer value. Your task is to produce a sum of money $x$ using the available coins in such a way that the number of coins is minimal. ---- ### 換零錢 (2) Consider a money system consisting of $n$ coins. Each coin has a positive integer value. Your task is to calculate the number of distinct ways you can produce a money sum $x$ using the available coins. --- ## What is Greedy 我全都要 ---- ### Definition + 依照每個步驟「當下」的狀況找到最佳解，但若從大局來看，**可能不是最佳的解決方案**。 + 所以為了嚴謹性，解題時不能只靠通靈，也要學會以數學證明 (like [數學歸納法](https://en.wikipedia.org/wiki/Mathematical_induction)) --- ## Exmamples of Greedy ---- ### Add all + 我現在有一個 set，裡面有 n 個數，每次我可以取出兩個數相加，再放回去，定義 cost 為每次選擇兩數的和，我要如何讓 cost 最小？ + 每次我都取最小的兩個數相加，會是對的 + 該用什麼資料結構做到這件事，每取一次就排序陣列？ ---- ### Priority Queue 優先隊列宣告方式： ```cpp= #include <queue> #include <vector> #include <iostream> using namespace std; int main() { priority_queue<int> max_pq; // 等同 priority_queue<int, vector<int>, less<int>> max_pq priority_queue<int, vector<int>, greater<int>> min_pq; max_pq.push(2); max_pq.push(5); max_pq.push(1); cout << max_pq.top() << endl; // 5 max_pq.pop(); } ``` ---- ### 排程問題 + 有點難解釋，放[題目](https://cses.fi/problemset/task/1629)。 + 要怎麼解？ +  把電影的**結束時間**由小排到大，然後遍歷一遍，如果該電影的時間與前面的人重疊，就不看。 ---- ### pair ```cpp= #include <iostream> #include <utility> // 包含 pair 的定義 using namespace std; int main() { // 創建一個 pair，包含一個 int 和一個 string pair<int, string> myPair(1, "Hello"); // 訪問元素 cout << "First: " << myPair.first << ", Second: " << myPair.second << endl; return 0; } ``` ---- ### 可分割背包問題 + 延續 0-1 背包問題，如果你可以選擇只拿 "一部分" 的物品 (means 價格與重量都會成比例)，要怎麼選才能使拿到的總價值最大？ + 先選 CP 值較高的物品 (價值/重量) --- ## 補充: Jupyter Notebook ---- ### Google Colab ---- ### Local environment ```bash= pip install jupyter ``` ```bash= # launch jupyter noteboook ``` --- ## 參考資料 ---- + [geekforgeeks](https://www.geeksforgeeks.org/) + [USACO](https://usaco.guide/) + [演算法筆記](https://web.ntnu.edu.tw/~algo/) --- ## Happy new year! ~~雖然是[聖誕節](https://www.youtube.com/watch?v=dQ_d_VKrFgM)先到~~