## Shoemaker’s Problem

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 = getTimeZero();
stages.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

Similar Posts: