Daily C/C++ dfs剪枝技巧

dfs剪枝技巧

这篇文章灵感来源于今天leetcode的每日一题

先看题

如果学过算法的同学应该知道，这道题是NP问题，是不存在多项式时间的解法的

最朴素的想法就是直接暴力搜索，对于每个任务来说，为他分配工人，那么复杂度就是m^n

这道题正确的做法是状压dp，以工人划分阶段，dp[i][j]表示i个工人，状态为j的最小值

转移就是dp[i][j] = min(dp[i - 1][k] + sum[j - k])

其中k是j的子集，sum[j - k]就是这个差集的任务的总时间

但是还有一种做法是二分+dfs，因为对于这道题的答案来说是有单调性的，即若i时间可以完成任务，则i+1一定也可以完成

那么我们二分答案，确定时间的上界，然后dfs查找是否存在一种分配方法，使得最大时间不超过这个上界

简单的代码就是类似这样

void dfs(int cur, int upper_bound, vector<int> &work_time) {
    for (int i = 0; i < k; k++) {
        if (work_time[i] + job[cur] > upper_bound)
            continue;
        work_time[i] += job[cur];
        dfs(cur + 1, upper_bound, work_time);
        work_time[i] -= job[cur];
    }
}

这个就是简单的回溯法，但是效率是不够的，我们需要优化这个dfs

如果在纸上稍微写一写，就可以发现，对于每个工人来说，他们本身是没有差异的，但是对于我们刚才写的代码来说，我们将其看做是有差异的个体了

为什么呢？考虑这样一种简单的情况，我们有两个工人和三个任务，那么答案[[1, 2], [3]] 和 [[3], [1, 2]] 是没有任何区别的

无论是一号工人做前两个任务，还是二号工人做前两个任务，其实是等价的

但是在我们的代码中去看，就可以发现，我们并没有消除这样的情况，如果输出答案的话，我们是会输出这样的情况的

所以我们要想办法优化，但是注意，对于代码的实现来说，工人i和工人j确实是不同的个体，因为他们的编号不同

所以我们的目标是找到一种策略，可以将这种情况排除

再在纸上跑一跑我们的算法可以发现，我们不希望出现的情况是 0 x 0 0 0 类似这样的 work_time

也就是说，对于这个任务x，如果他分配到第一个人那里失败了，那也就没有必要分配到后面人的手中

因为对于当前work_time为0的工人，他们是没有差异的，所以对任务x，我们只希望存在x 0 0 0 0这样的情况

更一般的说，如果对于工人i和j都没有分配任务，那么当前的任务只分配给i就足够了，因为i和j是等效的

或者也可以这样理解，我们通过每个工人的第一个任务，标志了他们的差异，没有任务的工人中，他们都是等效的，所以我们只取第一个就够了

那么这样我们就可以减少非常多无用的情况，从排列变成了组合

在代码中的表示就是，如果当前任务分配失败了且当前工人的工作时间是0，那么后面就没有必要继续执行了，因为后面工人的工作时间都是0，他们都是一样的

代码如下

void dfs(vector<int> &jobs, int k, int x, vector<int> &rec, int cur) {
    if (cur == jobs.size()) {
        ans = true;
        return;
    }
    if (ans) return;
    for (int i = 0; i < k; i++) {
        if (rec[i] + jobs[cur] > x) continue;
        rec[i] += jobs[cur];
        dfs(jobs, k, x, rec, cur + 1);
        rec[i] -= jobs[cur];
        if (rec[i] == 0)
            break;
    }
}