--- tags: 進階電腦系統理論與實作, NCKU Linux Kernel Internals, 作業系統 --- # 2020q3 Homework8 (quiz8) contributed by < `RusselCK` > ###### tags: `RusselCK` > [ dynamic programming & bitwise 操作 ＆ linked list ＆ 非連續記憶體操作 練習題](https://hackmd.io/@sysprog/2020-quiz8) ## Q1. LeetCode [1494. Parallel Courses II](https://leetcode.com/problems/parallel-courses-ii/) Given * the integer `n` representing **the number of courses** at some university labeled from `1` to `n` * the array dependencies where `dependencies[i] = [xi, yi]` represents a **prerequisite relationship** * that is, the course `xi` must be taken before the course `yi`. * **In one semester you can take at most `k` courses** as long as you have taken all the prerequisites for the courses you are taking. Return **the minimum number of semesters** to take all courses. Example: ![](https://i.imgur.com/JLdYvVi.png) ``` Input: n = 5, dependencies = [[2,1],[3,1],[4,1],[1,5]], k = 2 Output: 4 ``` ### 遞迴解 (**`recursive-nos1.c`**) ```c= #include <string.h> #include <limits.h> #define min(a, b) (((a) < (b)) ? (a) : (b)) static void solve(int i, int s, int k, int n, int s0, int s1, int *dp) { if ((k == 0) || (i == n)) { dp[s0 | s] = min(dp[s0 | s], dp[s0] + 1); return; } solve(i + 1, s, k, n, s0, s1, dp); if ((s1 >> i) & 1) solve(i + 1, s | 1 << i, k - 1, n, s0, s1, dp); } int minNumberOfSemesters(int n, int **dependencies, int dependenciesSize, int *dependenciesColSize, int k) { const size_t cap = 1 << n; int pre[cap]; memset(pre, 0, sizeof(pre)); for (int i = 0; i < dependenciesSize; i++) pre[dependencies[i][1] - 1] |= 1 << (dependencies[i][0] - 1); int dp[cap]; for (int i = 1; i < cap; i++) dp[i] = INT_MAX; dp[0] = 0; for (int s0 = 0; s0 < cap; s0++) { if (dp[s0] == INT_MAX) continue; int s1 = 0; for (int i = 0; i < n; i++) if (!((s0 >> i) & 1) && ((pre[i] & s0) == pre[i])) s1 |= 1 << i; solve(0, 0, k, n, s0, s1, dp); } return dp[cap - 1]; } ``` `#25` : `pre[cap]` : 課程 `cap` 的前導課程的 bit mask * `cap` = $2^n$ * 在 `pre[]` 中代表課程的 index ( 實際上只會用到 `0` ~ `n-1` ) * 在 `dp[]` 中代表已修過的課程的 bit mask * `#26` : (初始) 全為 `0` * for example : | `pre[0]` | `0...0 1110` | |:-----------:|:------------:| | `pre[4]` | `0...0 0001` | | `pre[o.w.]` | `0` | `#30` : ==`dp[cap]` : 完成`cap` 所需要的最少學期數== * `#31~33` : (初始) `dp[0] = 0`，其餘為 `INT_MAX` (infinity 的實作) * `s0` : 已修過的課程的 bit mask * `s1` : 目前可選擇的新課程 `#39~42` : 求`s1` * `((s0 >> i) & 1)` : 課程`i`是否已經修過了 * `(pre[i] & s0) == pre[i])` : 課程`i`的先修是否已經修完了 * `#42` : 若課程`i`滿足可選擇的條件，則加入`s1` `#44` : 從 `s1` 中找出至多 $k$ 門可選擇的課程，其 bit mask 為 `s` (從課程 `i = 0` 開始找起) > `solve(int i = 0, int s = 0, int k, int n, int s0, int s1, int *dp)` 若還有可以選擇課程的 quota 且 還有課程可以檢查 (即 `!((k == 0) || (i == n))`) : * `#12` : `solve(i + 1, s, k, n, s0, s1, dp);` >完成 dp 的精神 -- 建置表格 > 從 `s1` 中找出至多 $k$ 門可選擇的課程，其 bit mask 為 `s` (從課程 `i+1` 開始找起) * `#14~15` : 若 課程`i` 在 `s1` 的選項中 (即 `(s1 >> i) & 1`)，則將課程`i`納入`s`，並減少一個可選擇的 quota (即 `k - 1`)，接著找尋下一個可選擇的課程 (從課程 `i + 1` 開始找起) > `solve(i + 1, s | 1 << i, k - 1, n, s0, s1, dp);` 若沒有可以選擇課程的 quota 或 沒有課程可以檢查 (即 `((k == 0) || (i == n))`) : * `#8` : ==`dp[s0 | s] = min(dp[s0 | s], dp[s0] + 1);`== `#47` : `dp[cap - 1];` 即為修完所有課程至少需要的學期數 ### 非遞迴解 (**`iterative-nos1.c`**) ```c= #define min(a, b) (((a) < (b)) ? (a) : (b)) int minNumberOfSemesters(int n, int **dependencies, int dependenciesSize, int *dependenciesColSize, int k) { uint16_t prerequisite[n]; memset(prerequisite, 0, sizeof(prerequisite)); for (int i = 0; i < dependenciesSize; ++i) prerequisite[dependencies[i][1] - 1] |= 1 << (dependencies[i][0] - 1); const int cap = 1 << n; uint8_t dp[cap]; memset(dp, 1 << 6, cap); dp[0] = 0; for (uint32_t i = 0; i < cap; ++i) { uint32_t ready_for_take = 0; for (uint32_t j = 0; j < n; ++j) { if ((prerequisite[j] & i) == prerequisite[j]) ready_for_take |= 1 << j; } ready_for_take &= ~i; for (uint32_t j = ready_for_take; j; j = ready_for_take & (j - 1)) { if (__builtin_popcount(j) <= k) dp[i | j] = min(dp[i | j], dp[i] + 1); } } return dp[cap - 1]; } ``` `#9` :`prerequisite[n];` : 課程 `n` 的前導課程的 bit mask * 因為題目限制 `1 <= n <= 15`，因此使用 `uint16_t` 就足夠了 `#15` : `dp[cap]` : 完成`cap` 所需要的最少學期數 * 因為題目限制 `1 <= k <= n <= 15`，因此使用 `uint8_t` 就足夠了 > 甚至還太多，4 bits 就可以了 * `#16` : `memset(dp, 1 << 6, cap);` * `1 << 6` 可以換成 `14`，只要是 bit mask 有效範圍以外的數值即可 > leetcode 的測試的答案最多只到 13 ，所以最小換到 `13` 也能過 :::warning - [x] 理論上要寫成 `memset(dp, 1 << 6, sizeof(dp));`，但為何 `memset(dp, 1 << 6, cap);` 也可以? * 因為 `sizeof(dp)` = `cap` * 8 bits = `cap` * 1 bytes = **`cap` bytes** ::: :::info * [**`void *memset(void *s, int c, size_t n);`**](https://www.man7.org/linux/man-pages/man3/memset.3.html) * fills the first `n` **bytes** of the memory area pointed to by `s` with the constant byte `c`. ::: `#20~24` : 求 `s1` (目前可選擇的新課程) * `i` = `s0` (某個已修過的課程的 bit mask) * `ready_for_take` = `s1` `#26~30` : 非遞迴版本的 `solve(int i = 0, int s = 0, int k, int n, int s0, int s1, int *dp);` * `#26` : `ready_for_take &= ~i;` : 在尚未修完的課程中，所有符合前導規定且可選擇的新課程的 bitmask * `#27` : 由 `j = ready_for_take & (j - 1)` 來一個一個找尋選課數量不超過 `k` 的 bitmask ### 改良版的非遞迴解 (**`iterative-nos2.c`**) ```c= #define min(a, b) (((a) < (b)) ? (a) : (b)) int minNumberOfSemesters(int n, int **dependencies, int dependenciesSize, int *dependenciesColSize, int k) { const size_t cap = 1 << n; /* pre[i]: the bit representation of all dependencies of course i */ uint16_t pre[cap]; memset(pre, 0, sizeof(pre)); for (int i = 0; i < dependenciesSize; i++) pre[dependencies[i][1] - 1] |= 1 << (dependencies[i][0] - 1); /* i is the bit representation of a combination of courses. * dp[i] is the minimum days to complete all the courses. */ uint8_t dp[cap]; memset(dp, INIT, sizeof(dp)); // INIT = 0x5F dp[0] = 0; uint8_t count[cap]; memset(count, 0, sizeof(count)); for (uint32_t i = 0; i < cap; i++) { for (uint32_t j = 0; j < n; j++) if (i & (1 << j)) count[i]++; } for (uint32_t i = 0; i < cap; i++) { uint32_t b = 0; /* figure out "b", the bit representation of the all courses * that we can study now. Since we have i and pre[j], we know * course j can be studied if i contains all its prerequisites. */ for (uint32_t j = 0; j < n; j++) { if (COND && (pre[j] & i) == pre[j]) // COND = !(i & (1 << j)) b |= 1 << j; } if (count[b] <= k) { dp[i | b] = min(dp[i | b], dp[i] + 1); } else { for (uint32_t j = b; j; j = (j - 1) & b) { if (count[j] == k) dp[i | j] = min(dp[i | j], dp[i] + 1); } } } return dp[cap - 1]; } ``` `#20`: `memset(dp, INIT, sizeof(dp));` * 同前面所述，**INIT** 只要大於 `14` 即可 * 從選向上來看，**INIT = `0x5F`** `#23`: `count[cap];` : `cap` 代表的修課數量 :::warning * `#26~28` 換成 `count[i] = __builtin_popcount(i);` 可以更快 ::: `#37~40` : 求 `s1` (目前可選擇的新課程) * `b` = `s1` * `i` = `s0` (某個已修過的課程的 bit mask) * `j` (課程編號) * 做法與第一種方法相同，故 **COND = `!(i & (1 << j))`** `#41~42` : 若 `b` 可選的數量不超過 `k`，代表 `b` 挑出的課程都能用 1 學期就修完 :::warning * 這個 `if...else...` 可以省去第二種方法中一些多餘的執行步驟 ::: `#43~48` : 反之，就要從 `b` 中挑出至多 `k` 個課程的 bit mask `j` ## Q1. 進階題 ### LeetCode [1595. Minimum Cost to Connect Two Groups of Points](https://leetcode.com/problems/minimum-cost-to-connect-two-groups-of-points/) ## Q2. [Skip list](https://en.wikipedia.org/wiki/Skip_list)
Last changed by  
 
RusselCK
136

Read more

VSCode 套件安裝

C 語言開發 MinGW mingw-get-setup.exe mingw32-gcc-g++-bin mingw32-gdb-bin 檔案總管 > 電腦 > 內容 > 進階系統設定 > 環境變數 > Path 加入 \MinGW\bin

8/7/2022
ARGB To BW

contributed by < RusselCK > tags: RusselCK 【目標】 [ ] 2020q3 第 10 週測驗題 - 測驗 1 rgba.bng bw.png

10/2/2021
深入淺出物件導向分析與設計 筆記

範例程式碼 先修班 Chapter 0 歡迎光臨物件村 基礎篇 Chapter 1 偉大軟體的三步驟 Chapter 2 收集客戶需求

9/8/2021
TCL 讀書會(?

[x] TCL 教學 [x] TCL vscode 套件 Jimmy Mac VSCode 寫 C/C++ 教學 codechef jimmy helloworld.c

7/14/2021
Read more from RusselCK
Published on HackMD