二分 or 回溯 or bitmask dp
二分 or 回溯 or bitmask dp
公众号guangcity
发布于 2021-09-18 14:57:15
发布于 2021-09-18 14:57:15
二分 or 回溯 or bitmask dp
0.导语
在leetcode上有如下四种题目，做法类似，题目描述大同小异，涉及的算法包括：状态压缩dp、二分、递归、回溯，可算得上是比较好的几道题，今天来做个小结。
- 划分为k个相等的子集
- 在 D 天内送达包裹的能力
- 完成所有工作的最短时间
- 完成任务的最少工作时间段
1.698. 划分为k个相等的子集
题目描述：
给定一个整数数组 nums 和一个正整数 k，找出是否有可能把这个数组分成 k 个非空子集，其总和都相等。
示例 1：
输入：nums = [4, 3, 2, 3, 5, 2, 1], k = 4
输出：True
说明： 有可能将其分成 4 个子集（5），（1,4），（2,3），（2,3）等于总和。
提示：
1 <= k <= len(nums) <= 16
0 < nums[i] < 10000
这道题抽象为n个数，k组，每个组的sum一定为总sum/k。
每个数可以放在任何一个组中，因此是个分配问题，这里可以递归，我们可以放进去 再取出来，采用回溯完成所有分配，在分配中看看是否满足题意。
实现1：
class Solution {
public:
int k_;
int n_;
bool canPartitionKSubsets(vector<int>& nums, int k) {
k_ = k;
n_ = nums.size();
int sum = accumulate(nums.begin(), nums.end(), 0);
int target = sum / k;
if (sum % k) return false;
sort(nums.rbegin(), nums.rend());
return dfs(nums, vector<int>(k, 0), 0, target);
}
bool dfs(vector<int>& nums, vector<int> group, int pos, int target) {
if (pos >= n_) return true;
for (int i = 0; i < k_; i++) {
if (nums[pos] + group[i] > target) continue;
group[i] += nums[pos];
if (dfs(nums, group, pos + 1, target)) return true;
group[i] -= nums[pos];
if (group[i] <= 0) break;
}
return false;
}
};
实现2：dp+bit mask
采用bitmask方式，总共有0~(1<<n)-1种可能，从全不选到全选开始逐一尝试，使用dp[mask]表示在当前选择mask状态下可以完成划分为k个子集。
class Solution {
public:
vector<int> dp;
int tsum;
bool canPartitionKSubsets(vector<int>& nums, int k) {
int n = nums.size();
int sum = accumulate(nums.begin(), nums.end(), 0);
int target = sum / k;
if (sum % k) return false;
tsum = target;
dp = vector<int>(1 << n, -1);
return dfs(nums, target, k, 0);
}
int dfs(vector<int> &nums, int sum, int k, int mask) {
if (sum == 0) {
sum = tsum;
--k;
}
if (k == 0) {
return true;
}
if (dp[mask] != -1)
return dp[mask];
for (int i = 0; i< nums.size(); i++) {
if (!((1 << i) & mask) && nums[i] <= sum) {
int newMask = (1 << i) | mask;
if (dfs(nums, sum - nums[i], k, newMask)) return dp[mask] = true;
}
}
return dp[mask] = false;
}
};
2.1011. 在 D 天内送达包裹的能力
题目描述：
传送带上的包裹必须在 D 天内从一个港口运送到另一个港口。
传送带上的第 i 个包裹的重量为 weights[i]。每一天，我们都会按给出重量的顺序往传送带上装载包裹。我们装载的重量不会超过船的最大运载重量。
返回能在 D 天内将传送带上的所有包裹送达的船的最低运载能力。
示例 1：
输入：weights = [1,2,3,4,5,6,7,8,9,10], D = 5
输出：15
解释：
船舶最低载重 15 就能够在 5 天内送达所有包裹，如下所示：
第 1 天：1, 2, 3, 4, 5
第 2 天：6, 7
第 3 天：8
第 4 天：9
第 5 天：10
请注意，货物必须按照给定的顺序装运，因此使用载重能力为 14 的船舶并将包装分成 (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) 是不允许的。
提示：
1 <= D <= weights.length <= 5 * 104
1 <= weights[i] <= 500
实现：二分
检查当前包裹在D天能否以最大化容量m运载。
即：D个分组，每个分组的容量不超过m，如果每个分组都可以满足，不断压缩区间，继续寻找最少的运载量。
class Solution {
public:
int shipWithinDays(vector<int>& weights, int days) {
int sum = accumulate(weights.begin(), weights.end(), 0);
int l = 1, r = sum;
while (l < r) {
int m = (l + r) >> 1;
if (check(weights, days, m)) {
r = m;
} else {
l = m + 1;
}
}
return l;
}
bool check(vector<int>& weights, int D, int m) {
int day = 0;
for (int i = 0; i<weights.size(); i++) {
int j = i;
int s = 0;
while (j < weights.size() && weights[j] + s <= m) {
s += weights[j++];
}
day++;
if (day > D) return false;
i = j - 1;
}
return true;
}
};
3.1723. 完成所有工作的最短时间
题目描述：
给你一个整数数组 jobs ，其中 jobs[i] 是完成第 i 项工作要花费的时间。
请你将这些工作分配给 k 位工人。所有工作都应该分配给工人，且每项工作只能分配给一位工人。工人的 工作时间 是完成分配给他们的所有工作花费时间的总和。请你设计一套最佳的工作分配方案，使工人的 最大工作时间 得以 最小化 。
返回分配方案中尽可能 最小 的 最大工作时间 。
示例 1：
输入：jobs = [3,2,3], k = 3
输出：3
解释：给每位工人分配一项工作，最大工作时间是 3 。
示例 2：
输入：jobs = [1,2,4,7,8], k = 2
输出：11
解释：按下述方式分配工作：
1 号工人：1、2、8（工作时间 = 1 + 2 + 8 = 11）
2 号工人：4、7（工作时间 = 4 + 7 = 11）
最大工作时间是 11 。
提示：
1 <= k <= jobs.length <= 12
1 <= jobs[i] <= 1e7
实现1：二分
同1011题，k位工人在总工作时间m内完成工作。
class Solution {
public:
int minimumTimeRequired(vector<int>& jobs, int k) {
int sum = 0;
for (auto job : jobs) {
sum += job;
}
int l = 1, r = sum;
while (l < r) {
int m = (l + r) >> 1;
if (check(jobs, m, 0, vector<int>(k, 0))) {
r = m;
} else {
l = m + 1;
}
}
return l;
}
// k位工人在总和m工作时间内 能否完成任务
bool check(vector<nnint>& jobs, int m, int pos, vector<int> works) {
if (pos >= jobs.size()) return true;
for (int i = 0; i < works.size(); i++) {
if (works[i] + jobs[pos] > m) continue;
works[i] += jobs[pos];
if (check(jobs, m, pos + 1, works)) return true;
works[i] -= jobs[pos];
if (works[i] <= 0) break;
}
return false;
}
};
实现2：dfs+回溯
class Solution {
public:
int ans;
int minimumTimeRequired(vector<int>& jobs, int k) {
ans = 0x3f3f3f3f;
dfs(jobs, 0, vector<int>(k), 0);
return ans;
}
// k位工人在总和m工作时间内 能否完成任务
void dfs(vector<int>& jobs, int pos, vector<int> works, int cur) {
if (pos >= jobs.size()) {
ans = min(ans, cur);
return;
}
for (int i = 0; i < works.size(); i++) {
if (works[i] + jobs[pos] >= ans) continue;
works[i] += jobs[pos];
dfs(jobs, pos + 1, works, max(cur, works[i]));
works[i] -= jobs[pos];
if (works[i] <= 0) break;
}
}
};
实现3：bitmask
先求出k=1时，每种选择的sum，随后枚举状态，每个选择的子集取max，再取min。
class Solution {
public:
int minimumTimeRequired(vector<int>& jobs, int k) {
int n = jobs.size();
vector<int> maskSum(1 << n);
for (int mask = 0; mask < (1 << n); mask++) {
for (int i = 0; i < n; i++) {
if ((mask >> i) & 1) {
maskSum[mask] += jobs[i];
}
}
}
vector<vector<int>> dp(k + 1, vector<int>(1 << n));
for (int mask = 0; mask < (1 << n); mask++) {
dp[1][mask] = maskSum[mask];
}
for (int i = 2; i <= k; i++) {
for (int mask = 1; mask < (1 << n); mask++) {
dp[i][mask] = dp[i - 1][mask];
for (int subset = mask; subset; subset=(subset - 1) & mask) {
dp[i][mask] = min(dp[i][mask], max(maskSum[subset], dp[i-1][mask - subset]));
}
}
}
return dp[k][(1<<n) - 1];
}
};
4.1986. 完成任务的最少工作时间段
题目描述：
你被安排了 n 个任务。任务需要花费的时间用长度为 n 的整数数组 tasks 表示，第 i 个任务需要花费 tasks[i] 小时完成。一个 工作时间段 中，你可以 至多 连续工作 sessionTime 个小时，然后休息一会儿。
你需要按照如下条件完成给定任务：
如果你在某一个时间段开始一个任务，你需要在 同一个 时间段完成它。完成一个任务后，你可以 立马 开始一个新的任务。你可以按 任意顺序 完成任务。给你 tasks 和 sessionTime ，请你按照上述要求，返回完成所有任务所需要的 最少 数目的 工作时间段 。
测试数据保证 sessionTime 大于等于 tasks[i] 中的 最大值 。
示例 1：
输入：tasks = [1,2,3], sessionTime = 3
输出：2
解释：你可以在两个工作时间段内完成所有任务。
- 第一个工作时间段：完成第一和第二个任务，花费 1 + 2 = 3 小时。
- 第二个工作时间段：完成第三个任务，花费 3 小时。
提示：
n == tasks.length
1 <= n <= 14
1 <= tasks[i] <= 10
max(tasks[i]) <= sessionTime <= 15
实现1：二分
每个人物都可以被m个session种任意一个处理。
class Solution {
public:
int time;
int minSessions(vector<int>& tasks, int sessionTime) {
int n = tasks.size(), l = 1, r = n;
time = sessionTime;
while (l < r) {
int m = (l + r ) >> 1;
vector<int> sessions(m, 0);
if (check(sessions, m, tasks, 0)) {
r = m;
} else {
l = m + 1;
}
}
return l;
}
bool check(vector<int>& sessions, int m, vector<int>& tasks, int pos) {
if (pos >= tasks.size()) return true;
// 每个任务都可以被m个session中任意一个处理
for (int i = 0; i < m; i++) {
if (tasks[pos] + sessions[i] > time) continue;
sessions[i] += tasks[pos];
if (check(sessions, m, tasks, pos + 1)) return true;
sessions[i] -= tasks[pos];
if (sessions[i] <= 0) break; // 剪枝
}
return false;
}
};
实现2：dp+bitmask
dp[state]表示完成state任务所需要的 最少 数目的 工作时间段。
要求所有任务的最少工作时间段，即求dp[(1 << n) - 1]。
Base：每个state所需的时间段为初始为1。
迭代种遍历每个state的子集，dp[state]=min(dp[state], dp[subset] + dp[state-subset]);
class Solution {
public:
int minSessions(vector<int>& tasks, int sessionTime) {
int n = tasks.size();
vector<int> dp(1 << n, 0x3f3f3f3f);
for (int state = 0; state < 1 << n; state++) {
int sum = 0;
for (int i = 0; i < n; i++) {
if ((state >> i) & 1) {
sum += tasks[i];
}
}
if (sum <= sessionTime) {
dp[state] = 1;
}
}
for (int state = 0; state < (1 << n); state++) {
for (int subset = state; subset > 0; subset = (subset - 1) & state) {
dp[state] = min(dp[state], dp[subset] + dp[state - subset]);
}
}
return dp[(1 << n) - 1];
}
};
本节完~
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2021-09-05，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录