Minha pergunta está relacionada aessa outra discussão.

Estou tentando implementar esse algoritmo usando o programa dinâmico em uma chamada recursiva.

Declaração do problema:

O trabalho j começa emsj, termina emfje tem peso ou valorvj.

Dois trabalhos compatíveis se não se sobreporem.

Objetivo: encontre o subconjunto de peso máximo de trabalhos mutuamente compatíveis.

A solução proposta pelos livros é usar uma tabela de soluções para armazenar todos os suproblemas que serão reutilizados quando necessário durante uma chamada iterativa recursiva.

As etapas para resolver o problema são:

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]
    }

E este é o meu código (as partes relevantes):

vars globais:

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

/* job array */
job *jobs;

/* solutions table */
long *solutions;

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

- Classifique os trabalhos por horários de término para que 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);

Calcule p (1), p (2), ..., p (n) Onde p (j) = maior índice i <j, de modo que o trabalho i seja compatível com 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);

Executo meu programa em vários casos de teste com grandes dados (de 10k a 1m de trabalhos gerados aleatoriamente definidos) comparando minha saída com o resultado esperado. Em alguns casos, falha. Às vezes, minha saída é um pouco maior e outras, um pouco menor que o resultado esperado. Estou sentindo falta de algumas coisas, obviamente. Observe que, na maioria dos casos, minha saída está correta, então acho que há algumas condições especiais que não consigo lidar adequadamente

Não consigo descobrir onde está o problema.

Qualquer ajuda é apreciada

ATUALIZAR: Alterei a função recursiva para iterativa e agora o resultado está correto para todos os arquivos de teste. Mais uma vez, não consigo entender por que o recursivo não funciona