Problem description is http://acm.uva.es/p/v100/10026.html
Seems like a zero-one-knapsack, but a little more twisted. It took lots of time not because the complexity of the given problem, but because of the STL chores. -_-;;
I’d better read STL book again.
#include<iostream> #include<vector> #include<algorithm> using namespace std; #define MAX_INTEGER_VALUE 99999 // Represents each job class Job { public: int time; int fine; int ID; Job() {} Job(int ID, int time, int fine):ID(ID), time(time), fine(fine) {} }; class JobTimeLess { public: bool operator()(const Job &lhs, const Job &rhs) const { return lhs.time < rhs.time; } }; class EqualID { private: int ID; public: EqualID(Job job) { ID = job.ID; } bool operator()(const Job &j) const { return j.ID == ID; } }; class Stage { public: vector<Job> remained; int totalFine; Job jobFinished; Stage():totalFine(MAX_INTEGER_VALUE) {} Stage::~Stage() {} }; int totalTime() { return 3+1+2+5; } Stage getTimeZero() { Stage stage; stage.remained.push_back(Job(1,3,4)); stage.remained.push_back(Job(2,1,1000)); stage.remained.push_back(Job(3,2,2)); stage.remained.push_back(Job(4,5,5)); return stage; } void dumpStage(Stage &s) { cout << "Remained Jobs" << endl; vector<Job>::iterator i; for (i = s.remained.begin() ; i != s.remained.end() ; i++) cout <<"ID: " << (*i).ID << " Time: " << (*i).time << " Fine: " << (*i).fine << endl; } int computeFine(Stage &stage, Job job) { int fine = 0; vector<Job>::iterator i; for (i = stage.remained.begin() ; i != stage.remained.end() ; i++) { fine += (*i).fine; } return stage.totalFine + fine * job.time; } inline bool isLowerCost(Stage &target, Stage &stage, Job &job) { int fine = computeFine(stage, job); if (target.totalFine > fine) return true; // lexicographical ordering consideration else if (target.totalFine == fine && target.jobFinished.ID > job.ID) return true; return false; } int main() { vector<Stage> stages(totalTime() + 1); stages[0] = getTimeZero(); stages[0].totalFine=0; for (int timeIdx = 0 ; timeIdx < totalTime() ; timeIdx++) { vector<Job>::iterator i; Stage &stage = stages[timeIdx]; cout << "Time:" << timeIdx << endl; cout << "Considering..." << endl; dumpStage(stage); for (i = stage.remained.begin() ; i != stage.remained.end() ; i++) { Job job = *i; Stage &target = stages[timeIdx + job.time]; if (isLowerCost(target, stage, job)) { // Set finished job target.jobFinished = job; // New total fine target.totalFine = computeFine(stage, job); // Copying remained jobs, // excluding the job finished target.remained = vector<Job> (stage.remained); vector<Job>::iterator r = find_if(target.remained.begin(), target.remained.end(), EqualID(job)); target.remained.erase(r, r+1); } } } int timeIdx = totalTime(); cout << "Result" << endl; while(timeIdx > 0) { Stage stage = stages[timeIdx]; cout << "Time: " << timeIdx << " Job: " << stage.jobFinished.ID << endl; timeIdx = timeIdx - stage.jobFinished.time; } return 0; }
The answer is: 2 1 3 4
Leave a Reply