回溯算法流水作业调度问题c语言

回溯算法可以用来解决作业调度问题，以下是一个使用C语言实现的例子：

#include<stdio.h>
#include<stdlib.h>
#define MAX 20

int n, min = 9999;   //任务数和最小完成时间
int a[MAX][MAX];     //邻接矩阵
int visit[MAX];      //标记数组，记录每个任务是否已经被安排

void dfs(int k, int sum) {   //k为当前已安排的任务数，sum为当前完成时间
    if(k == n) {    //所有任务已经被安排
        if(sum < min) {     //如果当前完成时间比最小完成时间小，则更新最小完成时间
            min = sum;
        }
    } else {
        for(int i = 0; i < n; i++) {
            if(!visit[i]) {     //如果当前任务没有被安排，则尝试安排该任务
                visit[i] = 1;   //标记该任务已经被安排
                dfs(k+1, sum+a[k][i]);  //递归调用，继续安排下一个任务
                visit[i] = 0;   //回溯，将标记清除，以便尝试其他安排方案
            }
        }
    }
}

int main() {
    printf("请输入任务数：");
    scanf("%d", &n);
    printf("请输入邻接矩阵：\n");
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            scanf("%d", &a[i][j]);
        }
    }
    dfs(0, 0);  //从第0个任务开始安排，当前完成时间为0
    printf("最小完成时间为：%d\n", min);
    return 0;
}

这个程序中，使用邻接矩阵来表示任务之间的依赖关系，每次尝试安排一个任务时，遍历所有未被安排的任务，并递归调用dfs函数继续安排下一个任务。当所有任务都被安排完毕时，如果当前完成时间比最小完成时间小，则更新最小完成时间。这个程序的时间复杂度为O(n!)，因为需要遍历所有可能的安排方案。