Ma question concerne l'article this other discussion. J'essaie de mettre en œuvre cet algorithme en utilisant le programme dynamique dans un appel récursif.Intervalle pondéré Problème de planification et programme dynamique
Énoncé du problème:
Job j commence à sj, se termine à fj, et a un poids ou la valeur vj.
Deux travaux compatibles s'ils ne se chevauchent pas.
Objectif: trouver le sous-ensemble de poids maximal des travaux mutuellement compatibles.
La solution proposée par les livres est d'utiliser une table de solution pour stocker tous les problèmes qui seront réutilisés au besoin lors d'un appel itératif récursif.
Les étapes pour résoudre le problème sont:
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]
}
Et voici mon code (les parties pertinentes):
vars global:
typedef struct {
long start, stop, weight;
} job;
/* job array */
job *jobs;
/* solutions table */
long *solutions;
/* P(j) */
long *P;
emplois -sort par temps d'arrivée de sorte 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);
Calculer p (1), p (2), ..., p (n) Où p (j) = indice le plus élevé i < j tel que le travail i est compatible avec 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);
je lance mon programme contre plusieurs cas de test avec des données volumineuses (de 10k à 1m emplois générés au hasard mis) comparer ma sortie à l'attendu résultat. Dans certains cas, cela échoue. Parfois, ma sortie est un peu plus grande et parfois un peu inférieure au résultat attendu. Il me manque quelque chose, évidemment. Notez que dans la plupart des cas ma sortie est correcte donc je pense qu'il y a des conditions spéciales que je ne peux pas gérer correctement
Je ne peux pas savoir où est le problème.
Toute aide est appréciée
MISE À JOUR: j'ai changé la fonction récursive dans un processus itératif et maintenant le résultat est correct pour tous les fichiers de test. Encore une fois je ne peux pas comprendre pourquoi la récursive ne fonctionne pas
Il est nécessaire de trier l'entrée par l'heure de fin si nous utilisons une approche récursive. J'ai écrit une solution récursive qui prend un travail ou non sans trier les tâches d'entrée. – thebenman