加权区间调度问题与动态程序

我的问题与其他讨论有关 。

我正在尝试使用动态程序将该算法实现为递归调用。

问题陈述:

作业j从sj开始,在fj结束,并且具有重量或值vj

如果两个作业不重叠,则会兼容。

目标:找到相互兼容的作业的最大权重子集。

书籍提出的解决方案是使用解决方案表来存储所有问题,这些问题将在递归迭代调用期间在需要时重用。

解决问题的步骤是:

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

这是我的代码(相关部分):

全球大战:

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

– 按完成时间排序作业,使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); 

计算p(1),p(2),…,p(n)其中p(j)=最大索引i <j,使得作业i与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 = 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-计算-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); 

我针对几个具有大数据(从10k到1m随机生成的作业集)的测试用例运行我的程序,将我的输出与预期结果进行比较。 在某些情况下,它失败了。 有时我的输出有点大,有时比预期的结果要小一些。 我显然错过了一些事情。 请注意,在大多数情况下,我的输出是正确的,所以我认为有一些特殊条件我无法正确处理

我无法找出问题所在。

任何帮助表示赞赏

更新:我将递归函数更改为迭代函数,现在结果对于所有测试文件都是正确的。 再一次,我无法理解为什么递归的不起作用

让我们考虑一个简单的案例,一个工作。 你会打电话

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

然后,你有

  if (j == 0) return 0; 

computeOpt里面。 所以,你不能从一份工作中获得任何收益。

在一般情况下,由于上面的行,您似乎忽略了第一份工作。 if (j < 0)应该更好。

PS在进入“10k到1m随机生成的作业集”之前,始终测试简单和琐碎的案例。 它们更易于validation,更易于调试。