c++实现分支界限法的最佳调度问题

下面是使用 C++ 实现分支界限法的最佳调度问题的示例代码，其中使用了 STL 中的优先队列：

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

struct State {
    vector<int> times;  // k 台机器的工作时间
    int depth;          // 搜索树的深度
    int cost;           // 当前状态完成全部任务的时间
    bool operator<(const State& other) const {
        return cost > other.cost; // 优先队列按 cost 从小到大排序
    }
};

int best_time;   // 最优解
vector<int> tasks;  // n 个任务需要完成的时间
int k;          // k 台机器可并行工作

void branch_bound() {
    priority_queue<State> q; // 优先队列
    q.push(State{{0}, 0, 0}); // 初始状态
    while (!q.empty()) {
        State s = q.top(); q.pop();
        if (s.depth == tasks.size()) {
            best_time = s.cost;
            break; // 已找到最优解
        }
        for (int i = 0; i < k; i++) {
            State s2 = s;
            s2.times[i] += tasks[s.depth]; // 将任务分配给机器 i
            s2.depth++;
            s2.cost = *max_element(s2.times.begin(), s2.times.end()); // 更新完成全部任务的时间
            if (s2.cost < best_time) {
                q.push(s2); // 只加入可行状态
            }
        }
    }
}

int main() {
    int n;
    cout << "请输入任务数量 n 和可并行工作的机器数量 k：";
    cin >> n >> k;
    cout << "请输入每个任务需要完成的时间：";
    tasks.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> tasks[i];
    }
    branch_bound();
    cout << "最早完成时间为：" << best_time << endl;
    return 0;
}

在实际应用中，可以根据具体的问题进行优化，例如使用剪枝策略来加速搜索。