对于给定的n个作业制定最佳作业调度方案一个排列使其完成时间和达到最小使用c++回溯法实现

下面是C++回溯法实现最佳作业调度方案的代码：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MAXN = 10;

int n; // 作业数量
int time[MAXN]; // 每个作业需要的时间
vector<int> best_path; // 最优路径
int best_time = INT_MAX; // 最优完成时间

void dfs(vector<int>& path, int cur_time, int visited) {
    if (path.size() == n) { // 所有作业都安排完毕
        if (cur_time < best_time) { // 更新最优方案
            best_time = cur_time;
            best_path = path;
        }
        return;
    }
    for (int i = 0; i < n; i++) {
        if (!(visited & (1 << i))) { // 作业i还没有被安排
            path.push_back(i);
            dfs(path, cur_time + time[i], visited | (1 << i)); // 递归调用
            path.pop_back(); // 回溯
        }
    }
}

int main() {
    cout << "请输入作业数量：";
    cin >> n;
    cout << "请输入每个作业需要的时间：";
    for (int i = 0; i < n; i++) {
        cin >> time[i];
    }
    vector<int> path;
    dfs(path, 0, 0); // 从空路径开始搜索
    cout << "最优路径为：";
    for (int i = 0; i < n; i++) {
        cout << best_path[i] << " ";
    }
    cout << endl << "最优完成时间为：" << best_time << endl;
    return 0;
}

在这个程序中，我们使用了一个整数visited来表示哪些作业已经被安排，visited的二进制表示的第i位为1表示作业i已经被安排，为0表示作业i还没有被安排。每次递归调用时，我们从未被安排的作业中选择一个，将其添加到路径中，并将visited对应的位设为1。然后，我们递归调用dfs函数，继续搜索下一个作业。当所有作业都被安排时，我们更新最优方案，并返回。在回溯时，我们将路径中最后一个作业弹出，并将visited对应的位设为0，以便继续搜索其他方案。