用c++ 回溯法解决批作业调度问题

好的，以下是使用C++实现的回溯法求解批处理作业调度问题的代码。主要思路就是通过递归实现对每个排列的生成和计算完成时间和，然后比较得到最小值。

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

int n, res = INT_MAX; // n表示作业的个数，res表示完成时间和的最小值
vector<vector<int>> jobs; // 二维数组存储每个作业在两个机器上的处理时间

void backtrack(vector<int>& perm, int curTime) {
    if (perm.size() == n) { // 所有作业都排完了
        res = min(res, curTime); // 更新最小完成时间和
        return;
    }
    for (int i = perm.size(); i < n; i++) { // 枚举所有未排过的作业
        swap(perm[i], perm[perm.size()]); // 将未排过的作业移到排列末尾
        int t1 = jobs[perm.size()][0], t2 = jobs[perm.size()][1]; // 该作业在两个机器上的处理时间
        int finishTime1 = curTime + t1; // 该作业在机器1上的完成时间
        int finishTime2 = max(finishTime1, t2) + t2; // 该作业在机器2上的完成时间
        backtrack(perm, finishTime2); // 递归处理下一个位置
        swap(perm[i], perm[perm.size() - 1]); // 恢复原来的排列
    }
}

int main() {
    cin >> n;
    jobs.resize(n, vector<int>(2)); // 初始化jobs数组
    vector<int> perm(n);
    for (int i = 0; i < n; i++) {
        cin >> jobs[i][0] >> jobs[i][1];
        perm[i] = i; // 初始化排列为[0, 1, ..., n-1]
    }
    backtrack(perm, 0); // 从第一个位置开始递归
    cout << res << endl;
    return 0;
}