如题:
思路:
让工作去选人
画出解空间树即可
代码
#include <stdio.h>
#include <limits.h>
int n;
int c[21][21]; //将工作i分配给第j个人的费用为c[i][j]
int minCost = INT_MAX; //因为要求最小值,所以将minCost初始化为最大整数(int型)
int sum = 0; // 记录搜索过程中得到的工作费用和
int book[21]; // 用于标记一个人是否已被分配工作:book[i]=0表示没有被分配工作;book[i]=1表示已经被分配工作
void dfs(int t) {
if (t >= n) { //已经到达叶子结点,继续判断是否找到了最小总费用
if (minCost > sum) { // 没有找到最小总费用
minCost = sum; // 更新最小总费用
return;
}
}
for (int i = 0; i < n; i++) { //为第工作t安排人
if (!book[i]) { // 第i个人还没有被安排工作
book[i] = 1; // 将工作t分配给第i个人
sum += c[t][i]; // 更新总费用
if (sum < minCost) { // 如果当前得到的sum小于最小值,就向下搜索子树;否则剪枝
dfs(t + 1);
}
book[i] = 0; // 没有得到比minCost更小的和,回溯
sum -= c[t][i];
}
}
}
int main() {
scanf("%d", &n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
scanf("%d", &c[i][j]);
}
book[i] = 0;
}
dfs(0);
printf("%d\n", minCost);
return 0;
}
参考博客:
https://blog.csdn.net/weixin_48937140/article/details/121169372
https://blog.csdn.net/m0_46308522/article/details/110421351
标签:总费用,int,sum,minCost,问题,工作,book,分配 From: https://www.cnblogs.com/kirei7/p/17892990.html