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;
}
}
文章评论