Try  HackMD Logo HackMD

2020q3 Homework8 (quiz8)

contributed by < RusselCK >

tags: RusselCK

dynamic programming & bitwise 操作 & linked list & 非連續記憶體操作 練習題

Q1. LeetCode 1494. 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:

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

Input: n = 5, dependencies = [[2,1],[3,1],[4,1],[1,5]], k = 2
Output: 4 

遞迴解 (recursive-nos1.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 =
    2n
    • 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 : 若 課程is1 的選項中 (即 (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)

#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 也能過

    • 理論上要寫成 memset(dp, 1 << 6, sizeof(dp));,但為何 memset(dp, 1 << 6, cap); 也可以?
    • 因為 sizeof(dp) = cap * 8 bits = cap * 1 bytes = cap bytes

#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)

#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 代表的修課數量

  • #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 學期就修完

  • 這個 if...else... 可以省去第二種方法中一些多餘的執行步驟

#43~48 : 反之,就要從 b 中挑出至多 k 個課程的 bit mask j

Q1. 進階題

LeetCode 1595. Minimum Cost to Connect Two Groups of Points

Q2. Skip list