各种网站末班,深圳产品型网站建设,江苏国家住房和城乡建设部网站,包就业的培训学校算法设计
问题描述
有n#xff08;n≥1#xff09;个任务需要分配给n个人执行#xff0c;每个任务只能分配给一个人#xff0c;每个人只能执行一个任务。 第i个人执行第j个任务的成本是c[i][j]#xff08;1≤i#xff0c;j≤n#xff09;。求出总成本最小的分配方案 …算法设计
问题描述
有nn≥1个任务需要分配给n个人执行每个任务只能分配给一个人每个人只能执行一个任务。 第i个人执行第j个任务的成本是c[i][j]1≤ij≤n。求出总成本最小的分配方案
解题思路
回溯法解题的一般步骤 1针对给定的问题确定问题的解空间树问题的解空间树应至少包含问题的一个解或者最优解。 2确定结点的扩展搜索规则 3以深度优先的方式搜索解空间树并在搜索的过程中可以采用减枝函数来避免无效搜索。其中深度优先方式可以选择递归回溯或者迭代非递归回溯
通过将问题进行适当的转化得出解空间树为排列树这棵树每条完整路径都代表了一种解的可能。通过深度优先搜索这棵树枚举每种可能的解的情况找出能得到最小的花费结果。其中构造约束函数可以删除一些不可能的解从而大大提高程序效率
算法描述
1解空间 解空间为{x1x2x3x4……xn}其中xi1234……n表示第i个人安排的任务 2解空间树
#includestdio.h
#includecstring
#includequeueusing namespace std;
#define MAXN 20
#define INF 9999
//问题表示
int n4;//人或任务个数
int c[MAXN][MAXN]{{0,0,0,0,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 cost0; //临时解的成本
int bestx[MAXN]; //最优解
int mincostINF; //最优解成本
bool worker[MAXN]; //表示任务是否已经分配人员 void dfs(int i) //为第i个人员分配任务
{if(in) //如果达到叶子节点 {if(costmincost) //当前成本小于最小成本mincost{mincostcost; //更新最小成本for(int j1;jn;j) //遍历所有人员编号1~nbestx[j]x[j]; //将最佳人员编号给bestx}}else{for(int j1;jn;j) //遍历所有人员编号1~nif(!worker[j]) //如果没有分配任务{worker[j]true; //标记已经分配任务x[i]j; //将任务编号j分配给第i个人costc[i][j]; //更新成本加上分配任务成本dfs(i1); //调用dfs函数分配下一个人员worker[j]false; //标记该人员未分配任务x[j]0; //任务编号清零表示该人员未被分配任务cost-c[i][j]; //更新当前成本减去分配任务成本} }
}
int main(){memset(worker,0,sizeof(worker)); //memset函数将worker数组的所有元素初始化为0。dfs(1); //寻找最优方案printf(最优方案\n);for(int k1;kn;k) //从1循环到总人数nprintf(第%d个人安排任务%d\n,k,bestx[k]); //输出第k个人的任务分配printf(总成本%d\n,mincost); //输出最小成本return 0;}
