[动态编程] [状态压缩] [2 个选择] [广度搜索] 1494.并行课程 II

最编程 2024-03-02 13:52:14

...

作者推荐

视频算法专题

本文涉及知识点

动态规划汇总

状态压缩广度优先搜索

LeetCode1494. 并行课程 II

给你一个整数 n 表示某所大学里课程的数目，编号为 1 到 n ，数组 relations 中， relations[i] = [xi, yi] 表示一个先修课的关系，也就是课程 xi 必须在课程 yi 之前上。同时你还有一个整数 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 <= xi, yi <= n

xi != yi

所有先修关系都是不同的，也就是说 relations[i] != relations[j] 。

题目输入的图是个有向无环图。

状态压缩

15门课程。枚举最后一次选择（选择1到15门）和之前的选择（0到15门）。共多少种可能。暴力做法是：2³⁰。

枚举第一门课第二门课第三门课的可能

不包括0，共7种可能。

const int iMaxMask = (1 << 3)-1;

for (int mask = iMaxMask; mask; mask = (mask - 1) & iMaxMask)

{

char sz1[100],sz2[100];

_itoa_s(mask, sz1, 2);

_itoa_s(iMaxMask - mask, sz2, 2);

std::cout << “最后一次选择:\t” << sz1 << " 之前的选择:\t" << sz2 << std::endl;

}

最后一次选择: 111 之前的选择: 0

最后一次选择: 110 之前的选择: 1

最后一次选择: 101 之前的选择: 10

最后一次选择: 100 之前的选择: 11

最后一次选择: 11 之前的选择: 100

最后一次选择: 10 之前的选择: 101

最后一次选择: 1 之前的选择: 110

枚举第一、三、四

不包括0，共7种可能，不需要枚举16种可能。自动忽略了不可能存在的状态2。

const int iMaxMask = 1+4+8;

最后一次选择: 111 之前的选择: 0

最后一次选择: 110 之前的选择: 1

最后一次选择: 101 之前的选择: 10

最后一次选择: 100 之前的选择: 11

最后一次选择: 11 之前的选择: 100

最后一次选择: 10 之前的选择: 101

最后一次选择: 1 之前的选择: 110

枚举iMaxMask [0,2ⁿ)

总时间复杂度是:O(3ⁿ) 3¹⁵大约1.4e7。注意剪枝，否则容易超时。

动态规划

动态规划的状态表示

pre记录i学期能够完成的课程，dp记录i+1学期可以完成的课程。vHasDo记录已经完成的状态。状态没必要重复处理，i1<i2，如果某种状态i1学期能处理，那没必要i2学期处理。

空间复杂度:状态数 ,2ⁿ

时间复杂度: O(3ⁿ)

动态规划的转移方程

当前学期的课程，必须满足三个条件：

一，课程数小于等于k。

二，所有前置课程都已经完成。

三，这些课程没学习过。可以省略，会被淘汰。

预处理：

vPre[i] 表示第i门课需要的前面状态。

vNext[mask] 记录完成mask课程后，能够学习的课程。

动态规划的初始值

pre={0}

动态规划的填表顺序

i从0到大

动态规划的返回值

pre 包括(1<<n)-1时的i。

代码

核心代码

//通过 x &= (x-1)实现
int bitcount(unsigned x) {
  int countx = 0;
  while (x) {
    countx++;
    x &= (x - 1);
  }
  return countx;
}
class Solution {
public:
  int minNumberOfSemesters(int n, vector<vector<int>>& relations, int k) {
    const int iMaskCount = 1 << n;
    vector<int> vPre(n);
    for (const auto& v : relations)
    {
      vPre[v[1] - 1] |= 1 << (v[0] - 1);
    }
    vector<int> vNext(iMaskCount);
    for (int i = 0; i < iMaskCount; i++)
    {
      for (int j = 0; j < n; j++)
      {
        if ((vPre[j] & i) == vPre[j])
        {
          vNext[i] |= (1 << j);
        }
      }
    }
    vector<int> pre = { 0 };
    vector<bool> vHasDo(iMaskCount);
    for (int i = 0; ; i++)
    {
      vector<int> dp;
      for (const int& iPre : pre)
      {
        if (iPre + 1 == iMaskCount)
        {
          return i;
        }
        const int iRemain = (iMaskCount - 1) - iPre;
        const int iCanSel = iRemain& vNext[iPre];
        auto Add = [&](const int& cur)
        {
          const int iNew = cur | iPre;
          if (!vHasDo[iNew])
          {
            dp.emplace_back(iNew);
            vHasDo[iNew] = true;
          }
        };
        if (bitcount((unsigned int)iCanSel) <= k)
        {
          Add(iCanSel);
          continue;
        }
        for (int cur = iCanSel; cur; cur = (cur - 1) & iCanSel)
        {         
          if (bitcount((unsigned int)cur) == k)
          {
            Add(cur);
          }
        }
      }
      pre.swap(dp);
    }
    return -1;
  }
};

测试用例

template<class T>
void Assert(const T& t1, const T& t2)
{
  assert(t1 == t2);
}
template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
  if (v1.size() != v2.size())
  {
    assert(false);
    return;
  }
  for (int i = 0; i < v1.size(); i++)
  {
    Assert(v1[i], v2[i]);
  }
}
int main()
{ 
  int n, k;
  vector<vector<int>> relations;
  {
    Solution sln;
    n = 4, relations = { {2,1},{3,1},{1,4} }, k = 2;
    auto res = sln.minNumberOfSemesters(n, relations, k);
    Assert(3, res);
  }
  {
    Solution sln;
    n = 5, relations = { {2,1},{3,1},{4,1},{1,5} }, k = 2;
    auto res = sln.minNumberOfSemesters(n, relations, k);
    Assert(4, res);
  }
  {
    Solution sln;
    n = 11, relations = {}, k = 2;
    auto res = sln.minNumberOfSemesters(n, relations, k);
    Assert(6, res);
  }
}

动态规划

剪枝忽略非法的前者状态。

//通过 x &= (x-1)实现
int bitcount(unsigned x) {
  int countx = 0;
  while (x) {
    countx++;
    x &= (x - 1);
  }
  return countx;
}
template<class ELE,class ELE2>
void MinSelf(ELE* seft, const ELE2& other)
{
  *seft = min(*seft,(ELE) other);
}
template<class ELE>
void MaxSelf(ELE* seft, const ELE& other)
{
  *seft = max(*seft, other);
}
class Solution {
public:
  int minNumberOfSemesters(int n, vector<vector<int>>& relations, int k) {
    const int iMaskCount = 1 << n;    
    vector<int> vPre(n);
    for (const auto& v : relations)
    {
      vPre[v[1] - 1] |= 1 << (v[0] - 1);
    }
    vector<int> vNext(iMaskCount), vLen(iMaskCount);
    for (int i = 0; i < iMaskCount; i++)
    {
      vLen[i] = bitcount((unsigned int)i);
      for (int j = 0; j < n; j++)
      {
        if ((vPre[j] & i) == vPre[j])
        {
          vNext[i] |= (1 << j);
        }
      }
    }
    vector<int> vRet(iMaskCount,100);
    vRet[0] = 0;
    for (int i = 0; i < iMaskCount; i++)
    {   
            if(vRet[i] >= 100 )
            {
                continue;
            }
      const int iNeedStudy = (iMaskCount - 1) ^ i;//未学课程
      const int iCanStudy = iNeedStudy & vNext[i]; //只能学前置课程已学的课程
      if (vLen[iCanStudy] <= k)
      {
        MinSelf(&vRet[i| iCanStudy], vRet[i] + 1);
      }
      for (int j = iCanStudy; j; j= iCanStudy &(j-1))
      {//i是已学课程，j是本学期将学的课程  
        if (bitcount((unsigned )j) != k )
        {
          continue;
        }
        MinSelf(&vRet[i | j], vRet[i] + 1);
      }
    } 
    return vRet.back();
  }
};

2023年2月第一版

class Solution {

public:

int minNumberOfSemesters(int n, vector<vector>& relations, int k) {

m_iN = n;

m_iK = k;

m_iMaskNum = 1 << n;

m_vPreCourse.resize(n);

for (const auto& v : relations)

{

m_vPreCourse[v[1] - 1] |= (1 << (v[0] - 1));

}

m_vMinSemesters.resize(m_iMaskNum, m_iNotMay);

vector pre(1);

m_vMinSemesters[0] = 0;

for (int iSem = 0;; iSem++)

{

vector dp;

for (const auto& pr : pre)

{

if (pr + 1 == m_iMaskNum)

{

return iSem;

}

int iCanStudy = GetCanStudy(pr);

dfs(dp, pr, iCanStudy, iCanStudy, k,-1);

}

pre.swap(dp);

}

return 0;

}

inline int GetCanStudy(int preMask)const

{

int iCanStudy = 0;

for (int n = 0; n < m_iN; n++)

{

if (preMask & (1 << n))

{//之前已经学习

continue;

}

if ((m_vPreCourse[n] & preMask) != m_vPreCourse[n])

{//先行课程没有学习

continue;

}

iCanStudy |= (1 << n);

}

return iCanStudy;

}

void dfs(vector& dp, const int& preMask, const int& iCanStudy, int iRemain, int iLeve,int iPreN)

{

if ((0 == iLeve) || (0 == iRemain))

{

const int iNewMask = preMask |(iCanStudy - iRemain );

if (m_iNotMay != m_vMinSemesters[iNewMask])

{

return;

}

dp.push_back(iNewMask);

m_vMinSemesters[iNewMask] = m_vMinSemesters[preMask] + 1;

return;

}

for (int n = iPreN+1; n < m_iN; n++)

{

if (iRemain & (1 << n))

{

dfs(dp, preMask, iCanStudy, iRemain -(1 << n ), iLeve - 1,n);

}

vector m_vPreCourse;

vector m_vMinSemesters;

int m_iMaskNum;

int m_iK;

int m_iN;

const int m_iNotMay = 1000 * 1000;

};

2023年2月第二版

class Solution {

public:

int minNumberOfSemesters(int n, vector<vector>& relations, int k) {

m_iN = n;

m_iK = k;

m_iMaskNum = 1 << n;

m_vPreCourse.resize(n);

for (const auto& v : relations)

{

m_vPreCourse[v[1] - 1] |= (1 << (v[0] - 1));

}

m_vMinSemesters.resize(m_iMaskNum, m_iNotMay);

vector pre(1);

m_vMinSemesters[0] = 0;

for (int iSem = 0;; iSem++)

{

vector dp;

for (const auto& pr : pre)

{

if (pr + 1 == m_iMaskNum)

{

return iSem;

}

int iCanStudy = GetCanStudy(pr);

dfs(dp, pr, iCanStudy, iCanStudy, k, iCanStudy);

}

pre.swap(dp);

}

return 0;

}

inline int GetCanStudy(int preMask)const

{

int iCanStudy = 0;

for (int n = 0; n < m_iN; n++)

{

if (preMask & (1 << n))

{//之前已经学习

continue;

}

if ((m_vPreCourse[n] & preMask) != m_vPreCourse[n])

{//先行课程没有学习

continue;

}

iCanStudy |= (1 << n);

}

return iCanStudy;

}

void dfs(vector& dp, const int& preMask, const int& iCanStudy, int iRemain, int iLeve,int iCanSel)

{

if ((0 == iLeve) || (0 == iCanSel))

{

const int iNewMask = preMask |(iCanStudy - iRemain );

if (m_iNotMay != m_vMinSemesters[iNewMask])

{

return;

}

dp.push_back(iNewMask);

m_vMinSemesters[iNewMask] = m_vMinSemesters[preMask] + 1;

return;

}

while (iCanSel)

{

const int iNextCanSel = (iCanSel - 1)& iCanSel;

const int n = iCanSel - iNextCanSel;

iCanSel = iNextCanSel;

dfs(dp, preMask, iCanStudy, iRemain-n, iLeve - 1, iCanSel);

}

vector m_vPreCourse;

vector m_vMinSemesters;

int m_iMaskNum;

int m_iK;

int m_iN;

const int m_iNotMay = 1000 * 1000;

};

2023年7月版

using namespace std;

template

void OutToConsoleInner(const vector& vec, const string& strSep = " ")

{

for (int i = 0; i < vec.size(); i++)

{

if (0 != i % 25)

{

std::cout << strSep.c_str();

}

std::cout << setw(3) << setfill(’ ') << vec[i];

if (0 == (i + 1) % 25)

{

std::cout << std::endl;

}

else if (0 == (i + 1) % 5)

{

std::cout << strSep.c_str();

}

class CConsole

{

public:

上一篇： [YOLO Topic-10]：YOLO V5 - 超声检测/检测检验代码的命令行参数说明

下一篇： Gowin FPGA 教程系列 (1)：FPGA 和 ARM 开发环境设置

[动态编程] [状态压缩] [2 个选择] [广度搜索] 1494.并行课程 II

作者推荐

本文涉及知识点

LeetCode1494. 并行课程 II

状态压缩

枚举第一门课 第二门课第三门课 的可能

枚举第一、三、四

枚举iMaxMask [0,2n)

动态规划

动态规划的状态表示

动态规划的转移方程

动态规划的初始值

动态规划的填表顺序

动态规划的返回值

代码

核心代码

测试用例

动态规划

2023年2月第一版

2023年2月第二版

2023年7月版