1494. 并行课程 II (Hard)

问题描述

1494. 并行课程 II (Hard)

给你一个整数 n 表示某所大学里课程的数目，编号为 1 到 n ，数组 relations 中， relations[i] = [xᵢ, yᵢ] 表示一个先修课的关系，也就是课程 xᵢ 必须在课程 yᵢ 之前上。同时你还有一个整数 k 。

在一个学期中，你 最多 可以同时上 k 门课，前提是这些课的先修课在之前的学期里已经上过了。

请你返回上完所有课最少需要多少个学期。题目保证一定存在一种上完所有课的方式。

示例 1：

输入：n = 4, relations = [[2,1],[3,1],[1,4]], k = 2
输出：3
解释：上图展示了题目输入的图。在第一个学期中，我们可以上课程 2 和课程 3 。然后第二个学期上课程 1 ，
第三个学期上课程 4 。

示例 2：

输入：n = 5, relations = [[2,1],[3,1],[4,1],[1,5]], k = 2
输出：4
解释：上图展示了题目输入的图。一个最优方案是：第一学期上课程 2 和 3，第二学期上课程 4 ，第三学期上课
程 1 ，第四学期上课程 5 。

示例 3：

输入：n = 11, relations = [], k = 2
输出：6

提示：

• 1 <= n <= 15
• 1 <= k <= n
• 0 <= relations.length <= n * (n-1) / 2
• relations[i].length == 2
• 1 <= xᵢ, yᵢ <= n
• xᵢ != yᵢ
• 所有先修关系都是不同的，也就是说 relations[i] != relations[j] 。
• 题目输入的图是个有向无环图。

解题思路

本题很容易想到拓扑排序，然后基于拓扑排序进行贪心，但是这个做法是错的！本题实质上是个 NP-Hard 问题，只能暴力求解。

考虑状压 DP，其实很容易想到子问题。即先选择 $1, 2$，再选择 $3, 4, 5$（满足先修的要求）。用二进制数 $to$$study$ 表示当前要学习的课程的集合，用 $pre[j]$ 表示课程 $j$ 的先修课程的集合。那么递归函数即为 $dfs(to$$study, pre)$。

在本次递归中，我们先求出当前可以学习的课程的集合 $tmp$：

for (int i = 0; i < n; ++i) {
    if ((((1 << i) & to_study) != 0) && (pre[i] & to_study) == 0) {
        // 说明 i 在 to_study 中 且 i 的先修课程已经学习过了（或者没有先修课程）
        tmp = (tmp | (1 << i));
        ++cnt;
    }
}

如果 $tmp$ 的课程个数 $cnt <= k$，那么直接学习集合 $tmp$ 的所有课程，否则枚举 $tmp$ 的子集 $i$，如果子集 $i$ 的课程个数 $m$ 满足 $m <= k$，那么就学习该子集，那么下次递归中待学习的课程就可以用 $to$_$study \oplus i$ 表示。

枚举子集的方法参见 位运算与集合

C++ 中统计二进制数的 $1$ 的个数的库函数为 __builtin_popcount(i)。

代码

class Solution {
  public:
  	static auto dfs(int to_study, vector<int> &cach, int full, vector<int> &pre, int n, int k) -> int {
        if (to_study == 0) {
            return 0;
        }
  		if (cach[to_study] != -1) {
  			return cach[to_study];
  		}
  		int studied = (to_study ^ full);
  		int cnt = 0; // 统计可以学习的课程数
  		int tmp = 0; // 本次递归要学习的课程
  		for (int i = 0; i < n; ++i) {
  			if ((((1 << i) & to_study) != 0) && (pre[i] & to_study) == 0) {
  				// 说明 i 在 to_study 中 且 i 的先修课程已经学习过了（或者没有先修课程）
  				tmp = (tmp | (1 << i));
  				++cnt;
  			}
  		}
  		if (cnt <= k) {
  			cach[to_study] =  dfs(to_study ^ tmp, cach, full, pre, n, k) + 1;
  			return cach[to_study];
            // return dfs(to_study ^ tmp, cach, full, pre, n, k) + 1;
  		}
  		int res = INT_MAX;
  		for (int i = tmp; i != 0; i = (i - 1) & tmp) {
  			if (__builtin_popcount(i) <= k) {
  				res = min(res, dfs(to_study ^ i, cach, full, pre, n, k) + 1);
  			}
  		}
  		cach[to_study] = res;
  		return cach[to_study];

  	}
    int minNumberOfSemesters(int n, vector<vector<int>> &relations, int k) {
    	// 合集 i 表示要修的课程
    	// 合集 j 是 i 的子集，且 pre(j)（表示 j 的先修课程）与 i 没有交集，并且 size(j) <= k
    	vector<int> pre(n);
    	for (auto &vec : relations) {
    		int x = vec[0] - 1, y = vec[1] - 1; // 下标选择从 0 到 n - 1
    		pre[y] = (pre[y] | (1 << x));	
    	}
    	int full = (1 << n) - 1; // 全集
    	vector<int> cach(1 << n, -1);
    	return dfs(full, cach, full, pre, n, k);

    }
};