题目内容

调度器上有一组将调度的任务（$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. 优化位运算：

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

代码实现

以下是使用 C++ 实现的 DFS 枚举方法：

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

// 全局变量存储任务冲突信息
int jobNum;
ll executionTime[30];
ll conflict[30];
ll maxCount = 0;
ll minTotalTime = LLONG_MAX;

// DFS函数
void dfs(int index, ll currentMask, ll count, ll totalTime) {
    // 更新全局最优解
    if (count > maxCount || (count == maxCount && totalTime < minTotalTime)) {
        maxCount = count;
        minTotalTime = totalTime;
    }

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    // 输入任务数量
    cin >> jobNum;
    // 输入每个任务的执行时间
    for(int i = 0; i < jobNum; ++i){
        cin >> executionTime[i];
    }
    // 初始化冲突数组
    for(int i = 0; i < jobNum; ++i){
        conflict[i] = 0;
    }
    // 输入不亲和关系的数量
    int mutexNum;
    cin >> mutexNum;
    for(int i = 0; i < mutexNum; ++i){
        int u, v;
        cin >> u >> v;
        --u; --v; // 转换为0基索引
        conflict[u] |= (1LL << v);
        conflict[v] |= (1LL << u);
    }
    
    // 开始DFS
    dfs(0, 0, 0, 0);
    
    // 输出结果
    cout << minTotalTime;
    return 0;
}

正确思路

思路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}})$ 。

c++

#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <climits>
#include <algorithm>

using namespace std;

int jobNum;
vector<int> times;
unordered_map<int, unordered_set<int>> mutex;
int ans = 1;
int cost = INT_MAX;

bool check(int i, const unordered_set<int>& usd) {
    for (int u : usd) {
        if (mutex[u].count(i) || mutex[i].count(u)) return false;
    }
    return true;
}

void dfs(int i, unordered_set<int>& usd, int time) {
   //停止条件
    if (i >= jobNum) {
        if (ans <= (int)usd.size()) {
            if (ans < (int)usd.size()) {
                ans = usd.size();
                cost = time;
            } else if (ans == (int)usd.size()) {
                if (time < cost) {
                    cost = time;
                }
            }
        }
        return;
    }
    if (usd.size() + jobNum - i + 1 < ans) return ;
    dfs(i + 1, usd, time);
    if (check(i, usd)) {
        usd.insert(i);
        dfs(i + 1, usd, time + times[i]);
        usd.erase(i);
    }
}

int main() {
    cin.tie(0);
    cin >> jobNum;
    times.resize(jobNum);
    for (int i = 0; i < jobNum; i++) {
        cin >> times[i];
    }

    int mutexNum;
    cin >> mutexNum;

    for (int i = 0; i < mutexNum; i++) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        mutex[a].insert(b);
        mutex[b].insert(a);
    }

    unordered_set<int> usd;
    dfs(0, usd, 0);

    cout << cost << endl;

    return 0;
}