Deliberate Interim Planning Task and Dynamic Program

Question

My question is related to this other discussion .

I am trying to implement this algorithm using a dynamic program in a recursive call.

Description of the problem:

Task j begins with sj , ends with fj and has a weight or value vj .

Two jobs are compatible if they do not overlap.

Purpose: to find the maximum number of subsets of mutually compatible tasks.

The solution offered by the books is to use the solution table to store all add-ins that will be reused if necessary during a recursive iterative call.

Actions to solve the problem:

 Input: n, s1,...,sn , f1,...,fn , v1,...,vn Sort jobs by finish times so that f1 > f2 >... > fn. Compute p(1), p(2), ..., p(n) Where p(j) = largest index i < j such that job i is compatible with j. for j = 1 to n M[j] = empty <-- solution table M[j] = 0 M-Compute-Opt(j) { if (M[j] is empty) M[j] = max(wj + M-Compute-Opt(p(j)), M-Compute-Opt(j-1)) return M[j] } 

And this is my code (relevant parts):

global varna:

 typedef struct { long start, stop, weight; } job; /* job array */ job *jobs; /* solutions table */ long *solutions; /* P(j) */ long *P; 

-Sort tasks by end time so that f1> f2> ...> fn

  int compare(const void * a, const void * b) { const job *ad = (job *) a; const job *bd = (job *) b; return (ad->stop - bd->stop); } //Jobs is filled above by parsing a datafile qsort(jobs, njobs, sizeof(job), compare); 

Calculate p (1), p (2), ..., p (n) where p (j) = the largest index i <j, that the job i is compatible with j.

 /*bsearch for finding P(J) */ int jobsearch(int start, int high){ if (high == -1) return -1; int low = 0; int best = -1; int mid; int finish; while (low <= high){ mid = (low + high) /2 ; finish = jobs[mid].stop; if (finish >= start){ high = mid-1; }else{ best = mid; low = mid + 1; } } return best; } int best; for (i = 0; i < njobs; i++){ solutions[i] = -1l; //solutions table is initialized as -1 best = jobsearch(jobs[i].start,i-1); if (best != -1) P[i] = best; else P[i] = 0; } 

M-Computing-Opt (J):

 #define MAX(a, b) (((a) > (b)) ? (a) : (b)) /** * The recursive function with the dynamic programming reduction */ long computeOpt(long j) { if (j == 0) return 0; if (solutions[j] != -1l) { return solutions[j]; } solutions[j] = MAX(jobs[j].weight + computeOpt(P[j]), computeOpt(j - 1)); return solutions[j]; } long res = computeOpt(njobs-1); printf("%ld\n", res); 

I run my program according to several test scenarios with big data (from given given tasks from 10 to 1 m), comparing my result with the expected result. In some cases, it fails. Once my conclusion is a little more, and once a little less than the expected result. Obviously, I'm missing something. Please note that in most cases, my conclusion is correct, so I think there are some special conditions that I cannot handle normally

I do not know where the problem is.

Any help is appreciated

UPDATE: I changed the recursive function to iterative, and now the result is correct for the entire test file. Again I can't understand why recursive doesn't work

Answer 1

Consider the trivial case, one task. You will call

 long res = computeOpt(njobs-1); // computeOpt(0) 

Then you have

  if (j == 0) return 0; 

inside computeOpt . Thus, you cannot earn anything from one job.

In the general case, you seem to ignore the first job due to the above line. if (j < 0) should work better.

PS Always check simple and trivial cases before proceeding to the "task of given given tasks from 10 to 1 m". They are easier to check and easier to debug.