题目内容

调度器上有一组将调度的任务（$job$），大部分任务之间存在亲和关系，需要优先把具有亲和关系的任务调度到同一个核上面，不亲和的任务不能运行在同一个核上面；

现在给定一组待调度的任务（任务编号和任务执行时间），同时会给出任务之间不存在亲和关系的列表（未给出的默认是亲和关系）。请设计一个调度器，按照如下要求：

1、找出一组包含亲和任务数量最多的亲和调度任务组；

2、如果规则$1$有多个解，给出所有任务执行时间之和最小的。并输出该亲和调度任务组的所有任务执行时间之和。

亲和调度任务组定义：一组可以在同一核上面执行的亲和任务集合

解答要求

时间限制 $C/C++1000ms$ ，其他语言:$2000ms$ 内存限制 $C/C++256MB$，其他语言:$512MB$

输入

首行是一个整数$jobNum$，表示任务数量，任务编号$[1，jobNum]$，取值范围$[1,30]$

第二行$jobNum$个整数，表示每个任务的执行时间

第三行是一个整数$mutexNum$，表示不存在亲和关系的列表个数

接下来$mutexNum$行，每一行表示$1$对不亲和的任务编号，任务编号范围$[1,jobNum]$

输出

一个整数，表示所有任务的最短执行时间。

样例1

输入

3
2 3 10
1 
1 2

输出

12

解释:有$3$个待调度任务，任务$1$和任务$2$不亲和，不能在一个核上执行；

1.亲和调度任务组有：“任务$1$”“任务$2$”“任务$3$”，“任务$1$+任务$3$”，“任务$2$+任务$3$”；

2.包含任务数量最多的亲和调度任务组合有两种:“任务$1$+任务$3$”，或“任务$2$+任务$3$”；

3.两个任务的执行时间分别为$12$和$13$，选样执行时间较小的“任务$1$+任务$3$”，输出$12$。

样例2

输入

1
1
0

输出

1

解释:只有一个任务，返回这个任务的执行时间。

样例3

输入

3
2 3 10
3
1 2
2 3
1 3

输出

2

解释：有$3$个待调度任务，任务$1$和任务$2$、任务$2$和任务$3$、任务$1$和任务$3$不亲和，不能在一个核上执行；

1、亲和调度任务组有:“任务$1$”，“任务$2$”，“任务$3$”；

2、包含任务数量最多的亲和调度任务组合有$3$种:“任务$1$”，“任务$2$”，“任务$3$”；

3、$3$个场景的执行时间分别为$2、3、10$，选择执行时间较小的“任务$1$”，输出$2$。

【入门题】暴力拿分法2

本节课我们继续讨论骗分的方法。在前面章节我们学习了 DFS，也就是找遍所有的方法去得到正确答案，适用于范围小，因此我们可以用来骗分。

本题来自2024年8月21日华为机考真题。这里塔子哥给大家介绍一下华为机考：总共三道编程题，每道题的分值是(100,200,300)，通过华为机考需要至少150分。本题是秋招某次机考的最后一题(300分)。根据考生反映，使用本节课的骗分方法，我们可以拿到300 * 70% = 210 的高分，直接拿下机考!

题目理解

我们需要设计一个调度器，调度一组任务到不同的处理核上。任务之间存在亲和关系（默认情况下），即可以被调度到同一个核上；也存在不亲和关系（通过输入给出），即不能被调度到同一个核上。调度的目标是：

1. 最大化一个核上调度的亲和任务数量。
2. 在满足第1点的基础上，最小化这些任务的总执行时间。

最终，我们需要输出满足上述条件的任务组的总执行时间。

正确思路(感兴趣可以到本篇最下方进行查看)

• 思路1: 最大团搜索算法
• 思路2: 折半搜索(meet in the mid) + 子集dp

骗分思路（DFS + 2^n 枚举）

由于任务数量 jobNum 的范围为 [1, 30]，我们可以考虑使用深度优先搜索（DFS）结合位运算来枚举所有可能的任务组合。尽管 2^30（约 10 亿）个组合看起来庞大，但通过有效的剪枝和位运算优化，可以在合理的时间内解决此问题。

具体步骤：

1. 表示任务冲突：

   • 使用一个长度为 jobNum 的数组 conflict，其中 conflict[i] 是一个位掩码，表示任务 i 与哪些任务不亲和。如果 conflict[i] 的第 j 位为 1，表示任务 i 与任务 j 不亲和，不能同时调度到同一个核上。

2. DFS 枚举：

   • 从第一个任务开始，递归地选择是否将当前任务加入当前任务组。
   • 如果选择加入，需要确保当前任务与已选择的任务组中的所有任务没有冲突（通过位运算快速判断）。
   • 在每一步，记录当前任务组的大小和总执行时间，并更新全局最优解（最大任务数和最小总时间）。

3. 剪枝策略：

   • 如果当前任务组的大小加上剩余可选择的任务数量，无法超过当前已找到的最优任务组的大小，则可以提前剪枝，减少不必要的递归。

4. 优化位运算：

   • 通过使用位运算（如位掩码）来快速判断任务之间的冲突关系，提高运算效率。

Python 代码实现

# 定义全局变量存储任务冲突信息
jobNum = 0
executionTime = []
conflict = []
maxCount = 0
minTotalTime = float('inf')

# DFS函数
def dfs(index, currentMask, count, totalTime):
    global maxCount, minTotalTime
    # 更新全局最优解
    if count > maxCount or (count == maxCount and totalTime < minTotalTime):
        maxCount = count
        minTotalTime = totalTime

    # 逐个尝试添加任务
    for i in range(index, jobNum):
        # 检查任务i是否与当前任务组冲突
        if (currentMask & (1 << i)) == 0:
            # 检查任务i是否与已选任务冲突
            if (conflict[i] & currentMask) == 0:
                # 选择任务i
                dfs(i + 1, currentMask | (1 << i), count + 1, totalTime + executionTime[i])

def main():
    global jobNum, executionTime, conflict, maxCount, minTotalTime
    # 输入任务数量
    jobNum = int(input())
    executionTime = list(map(int, input().split()))

    # 初始化冲突数组
    conflict = [0] * jobNum

    # 输入不亲和关系的数量
    mutexNum = int(input())
    for _ in range(mutexNum):
        u, v = map(int, input().split())
        u -= 1  # 转换为0基索引
        v -= 1  # 转换为0基索引
        conflict[u] |= (1 << v)
        conflict[v] |= (1 << u)

    # 开始DFS
    dfs(0, 0, 0, 0)

    # 输出结果
    print(minTotalTime)

if __name__ == "__main__":
    main()

正确思路

思路1:最大团搜索算法

该问题就是最大团搜索算法的模板题。在搜索出每个最大团之后把团内节点的权值累加更新即可

思路2:折半搜索(meet in the mid) + 子集dp

前置知识:二进制枚举技巧

一个最简单的思路就是$O(2^n)$枚举所有子集，但是这样复杂度超了。我们观察到$n = 30$ , 自然想到可以将集合分成两个部分$|A| = |B| = 15$ ， 这样我们就可以分别对$|A| , |B|$ 暴力计算最大亲和的子集了.

此时的问题在于：如何解决$A,B$ 集合之间的不亲和情况。

例如来自$A$集合的$1001$ , 那也就是第1,4个节点被选中，假设他们对于B集合的第2，3个点不亲和。那么也就是二进制状态$0110$不亲和。反过来也就是$1001$亲和。那么我们就只需要求出$B$集合在$1001$限定状态下最多能互相亲和的个数。

这个个数可以使用子集$dp$求出，如果s本身就是亲和的，那么$dp[s] = |s|$ , 也就是s中二进制1的个数。

否则，考虑$dp[s] = max(dp[x])$ , x是s的真子集。且x二进制中个数恰好比s少1。 复杂度$O(2^{|A|})$

最后枚举$A$集合的亲和子集，匹配B集合的dp ， 加起来即可。总复杂度$O(2^{\frac{n}{2}})$

Python 代码实现（思路1）

from collections import defaultdict

jobNum = 0
times = []
mutex = defaultdict(set)
ans = 1
cost = float('inf')

def check(i, usd):
    for u in usd:
        if i in mutex[u] or u in mutex[i]:
            return False
    return True

def dfs(i, usd, time):
    global ans, cost
    # 停止条件
    if i >= jobNum:
        if ans <= len(usd):
            if ans < len(usd):
                ans = len(usd)
                cost = time
            elif ans == len(usd):
                if time < cost:
                    cost = time
        return

    if len(usd) + jobNum - i + 1 < ans:
        return

    # 不选择当前任务
    dfs(i + 1, usd, time)

    # 选择当前任务
    if check(i, usd):
        usd.add(i)
        dfs(i + 1, usd, time + times[i])
        usd.remove(i)

def main():
    global jobNum, times, mutex, ans, cost
    jobNum = int(input())
    times = list(map(int, input().split()))

    mutexNum = int(input())
    for _ in range(mutexNum):
        a, b = map(int, input().split())
        a -= 1  # 转换为0基索引
        b -= 1  # 转换为0基索引
        mutex[a].add(b)
        mutex[b].add(a)

    usd = set()
    dfs(0, usd, 0)

    print(cost)

if __name__ == "__main__":
    main()