流水作业调度 动态规划 C++

以下是使用C++实现流水作业调度问题的动态规划算法的示例代码：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 定义作业结构体
struct Job {
    int id; // 作业编号
    int time1; // 在M1机器上的加工时间
    int time2; // 在M2机器上的加工时间
};

// 动态规划算法求解流水作业调度问题
int flowShopScheduling(vector<Job>& jobs) {
    int n = jobs.size();
    
    // 创建二维数组dp，用于存储最优解
    vector<vector<int>> dp(n+1, vector<int>(2, 0));
    
    // 动态规划求解
    for (int i = 1; i <= n; i++) {
        dp[i][0] = dp[i-1][0] + jobs[i-1].time1; // 计算在M1机器上的总加工时间
    }
    
    for (int i = 1; i <= n; i++) {
        dp[i][1] = max(dp[i-1][1], dp[i][0]) + jobs[i-1].time2; // 计算在M2机器上的总加工时间
    }
    
    return dp[n][1]; // 返回最优解
}

int main() {
    int n;
    cout << "请输入作业数量：";
    cin >> n;
    
    vector<Job> jobs(n);
    cout << "请依次输入每个作业在M1和M2上的加工时间：" << endl;
    for (int i = 0; i < n; i++) {
        jobs[i].id = i + 1;
        cin >> jobs[i].time1 >> jobs[i].time2;
    }
    
    // 按照Johnson算法的规则对作业进行排序
    sort(jobs.begin(), jobs.end(), [](const Job& a, const Job& b) {
        return min(a.time1, a.time2) < min(b.time1, b.time2);
    });
    
    // 调用动态规划算法求解最优解
    int minTime = flowShopScheduling(jobs);
    
    cout << "完成所有作业所需的最少时间为：" << minTime << endl;
    
    return 0;
}