任务分配——回溯法
有n个任务需要分配给n个人执行，每个任务只能分配给一个人，每个人只能执行一个任务，第i个人执行第j个任务的成本是c[i][j](1<=i,j<=n）。求出总成本最小的一种方案。 【任务分配——回溯法】思路：解空间为子集树，用回溯法(dfs)搜索所有方案取最优解
//解空间为子集树
#include
#include
using namespace std;
#define INF 0x3f3f3f3f
#define MAXN 21
int n=4;
//任务数量
//第i个人执行第j个任务的成本
int c[MAXN][MAXN]={{0},{0,9,2,7,8},{0,6,4,3,7},{0,5,8,1,8},{0,7,6,9,4}};
int x[MAXN];
//临时解
int cost=0;
//临时解的成本
int bestx[MAXN];
//最优解
int mincost=INF;
//最优解的成本
bool worker[MAXN];
//worker[j]表示任务j是否已分配人员void dfs(int i){
if(i>n){
if(cost 推荐阅读
- 急于表达——往往欲速则不达
- 慢慢的美丽
- 《真与假的困惑》???|《真与假的困惑》??? ——致良知是一种伟大的力量
- 2019-02-13——今天谈梦想（）
- 考研英语阅读终极解决方案——阅读理解如何巧拿高分
- Ⅴ爱阅读，亲子互动——打卡第178天
- 低头思故乡——只是因为睡不着
- 取名——兰
- 每日一话（49）——一位清华教授在朋友圈给大学生的9条建议
- 广角叙述|广角叙述 展众生群像——试析鲁迅《示众》的展示艺术