Greedy Algorithm returning incorrect answer for Job Sequencing Problem

Question

Person X can only work for atmost 10 hours in a day. Given two arrays consisting of wages and duration of work of jobs, what is the maximum amount X can earn in a day?

One of the test cases was: wage array = {70,69,69,1} duration array = {7,5,5,1}

I know that the greedy algorithm works on the assumption that choosing the most lucrative option at each step satisfying the given constraints, will result in the optimal solution. But in this case the answer 71 in sub-optimal.

How should I modify the standard algorithm to also consider cases like these? Or is brute force the only way?

Answer 1

With the greedy algorithm you have to first calculate the ratio of value/weight of each jobs.

int wages[4] = {70, 69, 69, 1};
float durations[4] = {7, 5, 5, 1};
float ratios[4];
for (int i = 0; i < 4; i++)
{
  ratios[i] = wages[i]/durations[i];
}

After this you just iterate and pick jobs based on the ratios array as long as the sum of your work durations keep under your maximum work duration. Also it's important to consider if your problem is bounded or unbounded, as well as if fractional jobs are allowed.