回溯法经典例题--任务分配问题--C语言

任务分配问题是一种经典的组合优化问题，它的目标是将n个任务分配给n个人，使得总的分配成本最小。回溯法是解决任务分配问题的一种常用方法。具体来说，回溯法通过枚举所有可能的任务分配方案，并逐步剪枝，最终找到最优解。在C语言中，可以通过递归实现回溯法。下面是任务分配问题的C语言代码实现：

#include <stdio.h>
#define N 4

int min_cost = 1000000; // 初始化最小成本为一个较大的数
int cost[N][N] = {{9, 2, 7, 8}, {6, 4, 3, 7}, {5, 8, 1, 8}, {7, 6, 9, 4}}; // 任务分配成本矩阵

void assign(int i, int sum, int used[]) {
    if (i == N) { // 所有任务都已分配完毕
        if (sum < min_cost) { // 更新最小成本
            min_cost = sum;
        }
        return;
    }
    for (int j = 0; j < N; j++) {
        if (!used[j]) { // 第j个人还未被分配任务
            used[j] = 1; // 标记第j个人已被分配任务
            assign(i+1, sum+cost[i][j], used); // 递归分配下一个任务
            used[j] = 0; // 回溯，撤销第j个人的任务分配
        }
    }
}

int main() {
    int used[N] = {0}; // 初始化所有人都未被分配任务
    assign(0, 0, used); // 从第0个任务开始分配
    printf("最小成本为：%d\n", min_cost);
    return 0;
}