任务分配问题 | 分支限界法(限下界)
程序员文章站
2022-05-19 15:53:20
...
任务分配问题
成绩 10 开启时间 2020年04月14日 星期二 10:10 折扣 0.8 折扣时间 2020年05月30日 星期六 23:55 允许迟交 否 关闭时间 2020年05月30日 星期六 23:55 只有一组测试用例。
输入:第一行是操作员的人数n(4=<n<=11),接下来的n行里每行有n个数,分别表示第i名操作员完成第i项任务的时间。
输出:完成所有任务的最短时间。
测试输入 期待的输出 时间限制 内存限制 额外进程 测试用例 1 以文本方式显示
- 4↵
- 3 8 4 12↵
- 9 12 13 5↵
- 8 7 9 3↵
- 12 7 6 8↵
以文本方式显示
- 21↵
1秒 64M 0
此题当然可以使用回溯法解决,但是这里也可以用分支限界。不管怎样,都是遍历所有的决策树,只是分支限界这里是 bfs 遍历。我们针对每一个任务来讨论,为它分配未被选取的人员。
1、构造 min_cost 数组(贪心最小选取)
这里是求最小消耗时间,那么我们必须要限定下界,即该决策路可以达到的最小消耗。首先我们将第 i 件事的最小耗时存储在 min_cost [ i ] 中。
/* 找到数组a中的最小元素 */
int findMin(int a[]) {
int ans = INT_MAX;
for (int i = 1; i <= n; i++)
ans = min(ans, a[i]);
return ans;
}
int min_cost[MAXN]; //min_cost[i]:完成 i 的最小消耗
void setMinCost() {
for (int i = 1; i <= n; i++) {
int temp = findMin(Time[i]);
min_cost[i - 1] = temp;
}
}
2、对于决策点限定下界 key
对于每一个决策的节点:
- cur_cost 记录当前已经安排的事情的耗时
- rest_cost 记录未安排的事情所需的最短时间:
- 下界 key = cur_cost + rest_cost(key越小,该决策越可能找到最优解)
- 数组 vis[ ] 记录哪些人已经被选取过了
- step 表示当前已经完成 1..step 任务,接下来考虑 steap + 1 的任务
typedef struct node {
int key;
int cur_cost;
int rest_cost = 0; //完成step + 1..n的最小消耗
int step; //此节点已经完成 1..step 任务
bool vis[MAXN] = {false};
/* 构造函数1 */
node(int cc, int st) {
cur_cost = cc;
step = st;
for (int i = 0; i < n; i++)
if (!vis[i])
rest_cost += min_cost[i];
key = cur_cost + rest_cost;
};
/* 构造函数2 */
node(int cc, int st, bool v[]) {
cur_cost = cc;
step = st;
for (int i = step; i < n; i++)
if (!vis[i])
rest_cost += min_cost[i];
key = cur_cost + rest_cost;
for (int i = 1; i <= n; i++)
vis[i] = v[i];
};
/* 重载<运算符,以便于优先队列的创建 */
friend bool operator<(struct node x, struct node y) {
return x.key > y.key;
}
} Node;
3、广度优先搜索
建立一个优先队列,起初从根节点开始。之后每次选取 key 最小的节点讨论,依次考虑下一个事情的决策,并依次将决策子节点加入优先队列。
当取出节点 step = n - 1 时,说明此节点正在考虑最后一件事情,此时应该更新最小值。
当取出的节点 step = n 时,即节点(这是叶节点)已经分配完毕,最小值肯定已经取得!退出 bfs
void bfs() {
priority_queue<Node> Q;
Node head(0, 0);
while (head.step < n) {
int step = head.step;
int cur_cost = head.cur_cost;
/* 依次选取每一个人 */
for (int i = 1; i <= n; i++) {
int maybe = cur_cost + Time[step + 1][i];
if (head.vis[i] || maybe >= ans) //约束条件与限界条件
continue;
if (step == n - 1) //正在决策第n件事
ans = min(ans, maybe); //更新最小值
head.vis[i] = true;
Node temp(maybe, step + 1, head.vis);
Q.push(temp);
head.vis[i] = false;
}
/* 出队key最小的 */
head = Q.top();
Q.pop();
}
}
4、完整AC代码
注意:处理输入的时候,我把它反过来了。因为我是针对每一件事情的分配来讨论,所以希望一件事情分配每个人的消耗能储存在一行~
#include <cstdio>
#include <algorithm>
#include <queue>
#include <climits>
using namespace std;
#define MAXN 13
int Time[MAXN][MAXN]; //time[i][j]:第i件事给第j人做
int n;
/* 找到数组a中的最小元素 */
int findMin(int a[]) {
int ans = INT_MAX;
for (int i = 1; i <= n; i++)
ans = min(ans, a[i]);
return ans;
}
int min_cost[MAXN]; //min_cost[i]:完成 i 的最小消耗
int ans;
void setMinCost() {
for (int i = 1; i <= n; i++) {
int temp = findMin(Time[i]);
min_cost[i - 1] = temp;
}
}
void init() {
scanf("%d", &n);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
scanf("%d", &Time[j][i]);
setMinCost();
ans = INT_MAX;
}
typedef struct node {
int key;
int cur_cost;
int rest_cost = 0; //完成step + 1..n的最小消耗
int step; //此节点已经完成 1..step 任务
bool vis[MAXN] = {false};
node(int cc, int st) {
cur_cost = cc;
step = st;
for (int i = 0; i < n; i++)
if (!vis[i])
rest_cost += min_cost[i];
key = cur_cost + rest_cost;
};
node(int cc, int st, bool v[]) {
cur_cost = cc;
step = st;
for (int i = step; i < n; i++)
if (!vis[i])
rest_cost += min_cost[i];
key = cur_cost + rest_cost;
for (int i = 1; i <= n; i++)
vis[i] = v[i];
};
friend bool operator<(struct node x, struct node y) {
return x.key > y.key;
}
} Node;
void bfs() {
priority_queue<Node> Q;
Node head(0, 0);
while (head.step < n) {
int step = head.step;
int cur_cost = head.cur_cost;
/* 依次选取每一个人 */
for (int i = 1; i <= n; i++) {
int maybe = cur_cost + Time[step + 1][i];
if (head.vis[i] || maybe >= ans)
continue;
if (step == n - 1)
ans = min(ans, maybe);
head.vis[i] = true;
Node temp(maybe, step + 1, head.vis);
Q.push(temp);
head.vis[i] = false;
}
/* 出队key最小的 */
head = Q.top();
Q.pop();
}
}
int main() {
init();
bfs();
printf("%d\n", ans);
}
上一篇: CommonUtils工具类
推荐阅读
-
http://acm.hdu.edu.cn/showproblem.php?pid=3547昨天比赛的题目;立方体顶点染色有关问题
-
Photoshop 浅析选择常见问题-半选与转换
-
久攻不下市场,Windows Phone问题出在哪里
-
Mysql中使用DATE列的问题
-
几个关于php4的问题,如果接触过php4的老手请帮忙回答一下,不胜感激
-
关于IOS,UIViewController屏幕旋转 博客分类: 本文将详细讲解ios的旋转问题iphone ios旋转
-
spring容器初始化遇到的死锁问题解决
-
php分页实现的有关问题
-
PHP内置函数32位和64位平台兼容性问题_PHP教程
-
sql server-急!!!请教关于MySQL 与SQLserver2008R2数据库问题!