锐客网

  1. 首页 > it技术 > >

工作分配问题|工作分配问题 c++ 简单的递归回溯问题

题目描述
设有n件工作分配给n个人。将工作i分配给第j个人所需的费用为cij。试设计一个算法，为每一个人都分配一件不同的工作，并使总费用达到最小。设计一个算法，对于给定的工作费用，计算最佳工作分配方案，使总费用达到最小。
输入
输入数据第一行有1个正整数n (1≤n≤20)。接下来的n行，每行n个数，第i行表示第i个人各项工作费用。
输出
输出计算出的最小总费用。
样例输入
3
4 2 5
2 3 6
3 4 5
样例输出
9
这个题目很容易懂，知道让我们干什么，有些题目根本就不知道讲什么
方法一 这里比较难懂 swap(col[r],col[i]);

#include using namespace std; int s1=0,s2=INT_MAX,n; int col[25],a[25][25]; void dfs(int r){// r 表示行 if(r==n){ if(s1> n; for(int i=0; i> a[i][j]; } col[i]=i; // 0 1 2 3表示列 该加上下标为col[i]这以列i 这一行的数 } dfs(0); //因为为数组是下标为0开始放的。所以行就从0开始扫过去 cout<< s2 <

方法二 都是递归回溯的方法只是不同的表现形式 这比较好懂
#include using namespace std; int n,cost=0; int x[25],c[25][25]; // x[25] ：下标表示第几列，内容为0表示这一列代表的工作还没有工人做void work(int i,int count){ if(i>n && count>n; for(int i=1; i<=n; i++){ for(int j=1; j<=n; j++){ cin>>c[i][j]; x[j] = 0; //先全部赋值为0表示每一项工作都没有工人做过 } cost+=c[i][i]; //其实为感觉这个有点不合理直接把cost=INT_MAXint 类型里的最大值 } work(1,0); cout<

【工作分配问题|工作分配问题 c++ 简单的递归回溯问题】INT_MAX int 类型里的最大值

    推荐阅读


    上一篇：二分图匹配——最大匹配（匈牙利算法），完美匹配（最大权值匹配，KM算法）

    下一篇：C语言（使用指针输出数组元素）