Weighted Interval Scheduling problem & Dynamic pro

问题:

My question is related to this other discussion.

I'm trying to implement that algorithm using the dynamic program into a recursive call.

Problem statement:

Job j starts at sj, finishes at fj,and has weight or value vj.

Two jobs compatible if they don't overlap.

Goal: find maximum weight subset of mutually compatible jobs.

The solution proposed by books is to use a solution table to store all suproblems which will be reused when needed during a recursive o iterative call.

The steps to solve the problem are:

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 (the relevant parts):

global vars:

typedef struct {
    long start, stop, weight;
} job;

/* job array */
job *jobs;

/* solutions table */
long *solutions;

/* P(j) */
long *P;

-Sort jobs by finish times 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);

Compute p(1), p(2), ..., p(n) Where p(j) = largest index i < j such that 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-Compute-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 against several test cases with large data (from 10k to 1m random generated jobs set) comparing my output to the expected result. In some cases it fails. Sometime my output is e bit greater and sometime is a bit lesser than the expected result. I'm missing somethings obviously. Note that in the most of the cases my output is correct so I think there is some specials condition I can't handle properly

I cant't find out where the problem is.

Any help is appreciated

UPDATE: I changed the recursive function into an iterative one and now the result is correct for all test file. Again I can't understand why the recursive one not works

回答1:

Let's consider trivial case, one job. You'll call

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

Then, you have

    if (j == 0)
        return 0;

inside computeOpt. So, you can't earn anything from one job.

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

PS Always test simple and trivial cases before you go to "10k to 1m random generated jobs set". They are easier to verify and easier to debug.