最佳调度问题回溯法c语言

最佳调度问题指的是在一组任务中，如何安排任务的执行顺序，才能使任务的总执行时间最短。这个问题可以使用回溯算法进行求解。

回溯算法是一种基于深度优先搜索的算法。对于最佳调度问题，回溯算法的思路是：从第一个任务开始，依次枚举所有可能的下一个任务，计算当前任务序列的总执行时间，如果当前总执行时间已经大于已知的最小总执行时间，则剪枝，回溯到上一级任务，继续枚举其它可能的下一个任务；如果已经枚举完所有可能的下一个任务，则将当前任务序列作为最佳序列，并更新已知的最小总执行时间。然后回溯到上一级任务，继续枚举其它可能的下一个任务。

以下是最佳调度问题回溯法的C语言实现：

#include <stdio.h>
#define MAXN 100

int n;                  // 任务数
int p[MAXN];            // 任务的执行时间
int order[MAXN];        // 当前的任务序列
int bestOrder[MAXN];    // 最佳的任务序列
int minTime = 0x7fffffff;    // 最小总执行时间

void dfs(int curTime, int curPos) {
    if (curPos == n) {  // 已经排好了n个任务
        if (curTime < minTime) {
            minTime = curTime;
            for (int i = 0; i < n; i++) {
                bestOrder[i] = order[i];
            }
        }
        return;
    }
    for (int i = curPos; i < n; i++) {  // 枚举下一个任务
        int tmp = p[order[i]];
        for (int j = i; j > curPos; j--) {
            order[j] = order[j - 1];
        }
        order[curPos] = i;
        dfs(curTime + tmp * (n - curPos), curPos + 1);
        for (int j = curPos; j < i; j++) {
            order[j] = order[j + 1];
        }
        order[i] = i;
    }
}

int main() {
    printf("请输入任务数n：");
    scanf("%d", &n);
    printf("请输入%d个任务的执行时间：", n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &p[i]);
        order[i] = bestOrder[i] = i;
    }
    dfs(0, 0);
    printf("最佳的任务序列为：");
    for (int i = 0; i < n; i++) {
        printf("%d ", bestOrder[i] + 1);
    }
    printf("\n总执行时间为：%d\n", minTime);
    return 0;
}