用蛮力法求解任务分配问题,C语言代码

以下是用蛮力法求解任务分配问题的C语言代码：

#include <stdio.h>
#include <stdlib.h>

#define MAX 10

int n; // 任务数量
int cost[MAX][MAX]; // 任务分配矩阵
int min_cost = 999999; // 最小代价
int assignment[MAX]; // 任务分配方案
int solution[MAX]; // 当前解

void backtrack(int k, int curr_cost) {
    if (k == n) { // 找到一个可行解
        if (curr_cost < min_cost) {
            min_cost = curr_cost;
            for (int i = 0; i < n; i++) {
                assignment[i] = solution[i];
            }
        }
    } else {
        for (int j = 0; j < n; j++) {
            if (assignment[j] == -1) { // 如果任务未被分配
                solution[k] = j;
                assignment[j] = k;
                backtrack(k + 1, curr_cost + cost[k][j]);
                assignment[j] = -1; // 回溯，撤销任务分配
            }
        }
    }
}

int main() {
    printf("请输入任务数量：");
    scanf("%d", &n);

    printf("请输入任务分配矩阵：\n");
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &cost[i][j]);
        }
    }

    for (int i = 0; i < n; i++) {
        assignment[i] = -1;
    }

    backtrack(0, 0);

    printf("最小代价为：%d\n任务分配方案为：\n", min_cost);
    for (int i = 0; i < n; i++) {
        printf("任务 %d 分配给人员 %d\n", i + 1, assignment[i] + 1);
    }

    return 0;
}

该代码中，backtrack函数实现了回溯搜索，solution数组存储当前解，assignment数组存储任务分配方案。在主函数中，先输入任务数量和任务分配矩阵，然后初始化assignment数组为-1（表示未分配），最后调用backtrack函数求解任务分配问题。