数据结构与算法-独立任务最优调度问题_随笔

数据结构与算法-独立任务最优调度问题

题面：用2 台处理机A 和B 处理n 个作业。设第i 个作业交给机器A 处理时需要时间ai ，若由机器B 来处理，则需要时间bi。由于各作业的特点和机器的性能关系，很可能对于某些i，有ai ≥ bi ，而对于某些j,j≠i，有aj < bj 。既不能将一个作业分开由2 台机器处理，也没有一台机器能同时处理2 个作业。设计一个动态规划算法，使得这2 台机器处理完这n 个作业的时间最短(从任何一台机器开工到最后一台机器停工的总时间)。研究一个实例：(a1,a2,a3,a4,a5,a6)＝(2,5,7,10,5,2)；(b1,b2,b3,b4,b5,b6)＝(3,8,4,11,3,4) 。
数据输入：由文件input.txt 提供输入数据。文件的第1 行是1 个正整数n, 表示要处理n 个作业。接下来的2 行中，每行有n 个正整数，分别表示处理机A 和B 处理第i 个作业需要的处理时间。
数据输出：程序运行结束时，将计算出的最短处理时间输出到文件output.txt 中。
样例输入：
6

2 5 7 10 5 2

3 8 4 11 3 4
样例输出：15

代码

#include 
#include 
#include   //sort
#include 
#include 
#include   //双端队列，头可插，尾可插
#include 
#include 
#include 
#include 
#include  //数值的限制范围
//(double)clock() / CLOCKS_PER_SEC <= 0.95 限制0.95s跑完
using namespace std;

class Solver {
    //通用属性
public:
    string name;
    bool isDebug;

    Solver(string name, bool isDebug) {
        this->name = name;
        this->isDebug = isDebug;
    }

protected:
    static const int MAX = int(1e7);
    static const long long INF = (long long)1e18;
    //通用方法
protected:
    int QuickRead() {
        int num = 0, flag = 1;
        char ch = getchar();
        while (ch < '0' || ch > '9') {
            if (ch == '-') {
                flag = -1;
            }
            ch = getchar();
        }
        while (ch >= '0' && ch <= '9') {
            num = (num << 1) + (num << 3) + (ch ^ 48);
            ch = getchar();
        }
        return flag * num;
    }

    string GetTime() const {
        string str;
        tm t;
        time_t now;
        time(&now);
        localtime_s(&t, &now);
        str.append(to_string(t.tm_year + 1900));
        str.append("-");
        if ((t.tm_mon + 1) < 10) str.append("0");
        str.append(to_string(t.tm_mon + 1));
        str.append("-");
        if (t.tm_mday < 10) str.append("0");
        str.append(to_string(t.tm_mday));
        return str;
    }

public:
    void SaveCpp() {

        fstream input;
        fstream output;

        input.open("moota.cpp", ios::in);
        output.open(GetTime() + "-" + name + ".cpp", ios::out);

        char c = 'O';
        while (!input.eof()) {
            input.get(c);
            output << c;
        }

        input.close();
        output.close();

    }

protected:
    //待实现方法
    virtual void BeginPlay() {
    };

    virtual void Playing() {
    };

    virtual void EndPlay() {
    };
public:
    //外观模式
    void Play() {
        BeginPlay();
        Playing();
        EndPlay();
    }
};

class Player {
private:
    string name;
public:
    Player(string name) {
        this->name = name;
    }
    
    void Play(Solver* solver) {
        if (solver->isDebug) {
            cout<<"n"<SaveCpp();
        }
        solver->Play();
    }
};

class SpecialSolver : public Solver {
public:
    SpecialSolver(string name, bool isDebug): Solver(name, isDebug) {
    }

protected:
    void Debug(string message) {
        if (isDebug) { cout << message; }
    }

private: //实例属性
    int n;
    int a[MAX];
    int b[MAX];
    int dp[5];

private: //实例方法
    bool isJust(int index) {
        int sumI = 0, sumJ = 0;
        for (int i = 1; i <= index; ++i) {
            sumI += a[i];
            sumJ += b[i];
        }
        return sumI > sumJ;
    }

protected:
    virtual void BeginPlay() override {
        Debug("n---BeginPlay---n");
        cin >> n;
        for (int i = 1; i <= n; ++i) {
            cin >> a[i];
        }
        for (int i = 1; i <= n; ++i) {
            cin >> b[i];
        }
    };

    virtual void Playing() override {
        Debug("n---Playing---n");
        for (int i = 1; i <= n; ++i) {
            int newA = dp[1] + a[i];
            int newB = dp[2] + b[i];
            if (newA > newB) {
                dp[2] += b[i];
            }
            else if (newA == newB) {
                if (isJust(i)) {
                    dp[2] += b[i];
                }
                else {
                    dp[1] += a[i];
                }
            }
            else {
                dp[1] += a[i];
            }
        }
    };

    virtual void EndPlay() override {
        Debug("n---EndPlay---n");

        cout << max(dp[1], dp[2]);
    };
};

Player player("moota");
SpecialSolver specialSolver("独立任务最优调度问题", true);

int main() {
    player.Play(&specialSolver);
}

欢迎分享，转载请注明来源：内存溢出

原文地址: http://outofmemory.cn/zaji/5579492.html

数据结构与算法-独立任务最优调度问题

发表评论

评论列表（0条）