Untitled
unknown
plain_text
a year ago
3.8 kB
2
Indexable
#include <iostream> #include <fstream> #include <vector> #include <algorithm> #include <numeric> struct Unit { int p, r, d; }; struct Scheduler { public: std::vector<int> best; int upper_bound; int n; std::vector<Unit> units; }; void parse_input(const std::string &file, int &n, std::vector<Unit> &units, int& upperbound) { std::ifstream input(file); input >> n; units.resize(n); int p, r, d; int max_d = 0; for (int i = 0; i < n; ++i) { input >> p >> r >> d; units[i] = {p, r, d}; max_d = std::max(d, max_d); } upperbound = max_d + 1; input.close(); } std::vector<int> compute(const std::vector<int> &best, int n, std::vector<Unit> units) { if (best.empty()) { return {-1}; } int c = 0; std::vector<int> schedule(n, 0); for (int i: best) { int t = std::max(c, units[i].r); c = t + units[i].p; schedule[i] = t; } return schedule; } bool branch_and_bound(std::vector<int> &scheduled_tasks, const std::vector<int> ¬_sch_tasks, int len_of_partial_sch, Scheduler &scheduler) { int p_sum = 0; // missed deadline: (∃ Tj ∈ V: max{c, rj} + pj > dj) ⇒ prune this node for (int i: not_sch_tasks) { if (scheduler.units[i].d < std::max(len_of_partial_sch, scheduler.units[i].r) + scheduler.units[i].p) { return false; } p_sum += scheduler.units[i].p; } // bound on the solution if (scheduled_tasks.size() == scheduler.n) { if (scheduler.upper_bound >= len_of_partial_sch) { scheduler.best = scheduled_tasks; scheduler.upper_bound = len_of_partial_sch; } return false; } int r_min = 1000000000; for (int task: not_sch_tasks) { r_min = std::min(r_min, scheduler.units[task].r); } int lower_bound = std::max(len_of_partial_sch, r_min) + p_sum; if (lower_bound >= scheduler.upper_bound) { return false; } // decomposition, c ≤ min(Tj∈V) {rj }) ⇒ do not backtrack. bool part_sol = false; if (len_of_partial_sch <= r_min) { part_sol = true; } for (int i: not_sch_tasks) { scheduled_tasks.push_back(i); std::vector<int> new_not_sch_tasks; for (int task: not_sch_tasks) { if (task != i) { new_not_sch_tasks.push_back(task); } } if (branch_and_bound(scheduled_tasks, new_not_sch_tasks, std::max(len_of_partial_sch, scheduler.units[i].r) + scheduler.units[i].p, scheduler)) { return true; } scheduled_tasks.pop_back(); } return part_sol; } int main(int argc, char *argv[]) { if (argc != 3) { std::cerr << "Usage: " << argv[0] << " input_file output_file\n"; return 1; } int n, upperbound; std::vector<int> best; std::vector<Unit> units; parse_input(argv[1], n, units, upperbound); Scheduler scheduler = {best, upperbound, n, units}; std::vector<int> scheduled, not_scheduled(n); std::iota(not_scheduled.begin(), not_scheduled.end(), 0); std::sort(not_scheduled.begin(), not_scheduled.end(), [&units](const int& a, const int& b) { return units[a].d - units[a].p < units[b].d - units[b].p; }); branch_and_bound(scheduled, not_scheduled, 0, scheduler); std::vector<int> res = compute(scheduler.best, n, scheduler.units); // for (int s: res) { // std::cout << s << std::endl; // } std::ofstream output(argv[2]); for (int s: res) { output << s << std::endl; } return 0; }
Editor is loading...
Leave a Comment