算法导论—动态规划之装配线部署

算法导论—动态规划之装配线调度

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
const int maxn = 10000;
int f1[maxn], f2[maxn]; //保存最优解
int a[3][maxn];         //每个装配站所用的时间
int t[3][maxn];         //装配线调度所用的时间
int l[3][maxn];         //保存选择的路线，以便打印路径。
int e1, e2;
int x1, x2;
int res;
int res1;               //代码最后一个装配站的标号是1还是2.
int n;                  // 代表装配线的长度。
//P193页（第二版）
void init() {
    scanf("%d%d", &e1, &e2);
    for(int i = 1; i<=n-1; i++) {
        scanf("%d%d", &a[1][i], &a[2][i]);
        scanf("%d%d", &t[1][i], &t[2][i]);
    }
    scanf("%d%d", &a[1][n], &a[2][n]);
    scanf("%d%d", &x1, &x2);
}

int fast_way(){
    f1[1] = e1 + a[1][1];
    f2[1] = e2 + a[2][1];
    for(int i = 2; i<=n; i++) {
        if(f1[i-1]+a[1][i] <= f2[i-1]+a[1][i]+t[2][i-1] ) {
            f1[i] = f1[i-1] + a[1][i];
            l[1][i] = 1;
        }else{
            f1[i] = f2[i-1] + a[1][i] + t[2][i-1];
            l[1][i] = 2;
        }
        if(f2[i-1]+a[2][i] <= f1[i-1]+a[2][i]+t[1][i-1]){
            f2[i] = f2[i-1] + a[2][i];
            l[2][i] = 2;
        }else{
            f2[i] = f1[i-1] + a[2][i] + t[1][i-1];
            l[2][i] = 1;
        }
    }
    if(f1[n]+x1<=f2[n]+x2){
        res = f1[n] + x1;
        res1 = 1;
    }else{
        res = f2[n] + x2;
        res1 = 2;
    }
    return res;
}

void print_station(){//打印路径
    int i = res1;
    int j;
    printf("line:%d, station:%d\n", i, n);
    for( j = n; j >= 2; j--) {
        i = l[i][j];
        printf("line:%d, station:%d\n", i, j-1);
    }
}

int main()
{
    while(scanf("%d", &n) != EOF) {
        init();
        int result = fast_way();
        cout << result << endl;
        print_station();
    }
    return 0;
}
/*****************************
测试数据：P193算法导论（第二版）
6
2 4
7 8
2 2
9 5
3 1
3 6
1 2
4 4
3 2
8 5
4 1
4 7
3 2
****************************/