问题

拓扑排序在此题不适合的原因，因为会存在多个入度为 0 的节点，可能出现选取的并不是最优解的情况。

举例： [ [ 1, 4] [3, 4] [ 2, 5] [4, 5] [ 4, 6] [ 5, 6]] K = 2

当第一次选取的为 1，2 时，并不是最优解必须选取 1， 3 或者 2，4 才可

方案一

以 bitmask 来记录当前学习的课程，动态规划来得到最合理的安排（即最小的用时）

全部课程修完，则用 dp[ 2 ** n - 1] 来表示。
全部的状态为 0 -> 2 ** n - 1

前置 - 依赖关系

这一步需要记录依赖关系的状态数据

将依赖的前置课程，以二进制中 1 的状态进行存储依赖关系 i, pre preq[I-1] |= 1 << (pre - 1)

状态转移

1. 定义状态

dp[i] 表示当前的课程组合学习，所需要的最小步数

i 的范围 0 -> 2 ** n - 1 dp[0] = 0

2. 寻找当前可以学习的课程

如：当前的状态 i ，需要根据 i ，寻找当前可以学习的课程。因为前面已经知道了每门课程的前置课程内容。判断其前置课程是否已经满足，可通过如下的二进制操作来判断：

i & pre[j] = pre[j]

当满足上述等式时，表示当前课程 j 可以进行学习了。

这一步中，可将所有满足的课程采用二进制移位的方式，记录在一个数字 tolearn 中。如课程 j 现在可以学习了，则

tolearn |= 1 << j

3. 学习当前满足的课程组合

题目中限制了当前只能学习 k 门课程。所以需要遍历得到 tolearn 中可以学习的课程组合，即是寻找其二进制中存在 1 的组合数目，并满足 1 的个数需要小于等于 k 。

这里可通过如下代码得到其子组合：

s = tolearn
while s:
  s = (s - 1) & tolearn

具体可以查看： Submask Enumeration - Competitive Programming Algorithms

这里需要计算 s 中二进制 1 的个数，需要小于等于 k ，得到满足的 s 后，状态转移方程为：

dp[ i | s ]  = min (dp [ i | s ] ,  dp[i] + 1)

代码实现

def minNumberOfSemesters(self, n: int, dependencies: List[List[int]], k: int) -> int:
    from collections import defaultdict
    dep = defaultdict(int)
    # 保存当前课程的前置依赖关系
    for [pre, cur] in dependencies:
        dep[cur - 1] |= 1 << (pre - 1)
    # 满足当前状态的 i, 所需要的最小步数
    dp = [n] * (1 << n)
    dp[0] = 0
    for i in range(1 << n):
        # 获取当前 i 可以学的前置课程。
        to_learn = 0
        for j in range(n):
            if (1 << j) & i: continue
            if i & dep[j] == dep[j]:
                to_learn |= 1 << j
        to_learn &= ~i
        s = to_learn

        while s > 0:
            if bin(s).count("1") <= k:
                dp[i | s] = min(dp[i | s], dp[i] + 1)
                # s 的二进制包含 1 的子集集合
            s = (s - 1) & to_learn
        # print(i, ex)
    return dp[-1]

方案二

此方案主要优化这个子组合的获取。思路： 1. 获取当前可以学习的课程，将其放置在 list 数组中 2. 判断 list 数组的大小，若其长度小于等于 k 值，则全部学习 3. 若 List 数组的长度大于 k 值，利用 Python 的 itertools 库中的 combination 来获取长度为 k 的组合数。

def minNumberOfSemesters(self, n: int, dependencies: List[List[int]], k: int) -> int:
    from collections import defaultdict
    from itertools import combinations
    dep = defaultdict(int)
    # 保存当前课程的前置依赖关系
    for [pre, cur] in dependencies:
        dep[cur - 1] |= 1 << (pre - 1)
    # 满足当前状态的 i, 所需要的最小步数
    dp = [n] * (1 << n)
    dp[0] = 0
    for i in range(1 << n):
        to_learn_list = []
        for j in range(n):
            if (1 << j) & i: continue
            if i & dep[j] == dep[j]:
                to_learn_list.append(j)
        if len(to_learn_list) <= k:
            s = 0
            for j in to_learn_list:
                s |= 1 << j
            dp[i | s] = min(dp[i | s], dp[i] + 1)
        else:
            for sub_list in combinations(to_learn_list, k):
                s = 0
                for j in sub_list:
                    s |= 1 << j
                dp[i | s] = min(dp[i | s], dp[i] + 1)
    return dp[-1]

方案二

将状态的一次遍历，转化 bfs 的思想来完成。

class Solution:
    def minNumberOfSemesters(self, n: int, dependencies: List[List[int]], k: int) -> int:
        from collections import defaultdict
        from itertools import combinations
        dep = defaultdict(int)
        # 保存当前课程的前置依赖关系
        for [pre, cur] in dependencies:
            dep[cur - 1] |= 1 << (pre - 1)
        # 满足当前状态的 i, 所需要的最小步数
        dp = [n] * (1 << n)
        dp[0] = 0
        from collections import deque
        queue = deque()
        queue.append((0, 0))
        while queue:
            (pre, step) = queue.pop()
            to_learn_list = []
            for j in range(n):
                if (1 << j) & pre: continue
                if pre & dep[j] == dep[j]:
                    to_learn_list.append(j)
            if len(to_learn_list) <= k:
                s = 0
                for j in to_learn_list:
                    s |= 1 << j
                if dp[pre | s] > dp[pre] + 1:
                    dp[pre | s] =  dp[pre] + 1
                    queue.append((pre | s, dp[pre|s]))
            else:
                for sub_list in combinations(to_learn_list, k):
                    s = 0
                    for j in sub_list:
                        s |= 1 << j
                    if dp[pre | s] > dp[pre] + 1:
                        dp[pre | s] = min(dp[pre | s], dp[pre] + 1)
                        queue.append((pre | s, dp[pre | s]))
            # print(pre)
        return dp[-1]

alighters

程序、写作、人生

1494. Parallel Courses II

问题

方案一