我的问题与 this other discussion 有关.
我正在尝试使用动态程序在递归调用中实现该算法。
问题陈述:
作业 j 开始于 sj
,结束于 fj
,并且具有权重或值 vj
。
如果两个工作不重叠,则它们是兼容的。
目标:找到相互兼容的作业的最大权重子集。
书上提出的解决方案是使用解决方案表来存储所有的superproblem,这些superproblem将在递归或迭代调用期间在需要时重复使用。
解决问题的步骤是:
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 <= 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);
我针对多个具有大数据(从 10k 到 1m 随机生成的作业集)的测试用例运行我的程序,将我的输出与预期结果进行比较。在某些情况下它会失败。有时我的输出比预期结果大一点,有时比预期结果小一点。我显然遗漏了一些东西。请注意,在大多数情况下,我的输出是正确的,所以我认为有些特殊情况我无法正确处理
我找不到问题出在哪里。
感谢任何帮助
更新: 我将递归函数更改为迭代函数,现在所有测试文件的结果都是正确的。 我还是不明白为什么递归的不起作用
最佳答案
让我们考虑一个简单的案例,一份工作。你会打电话
long res = computeOpt(njobs-1); // computeOpt(0)
然后,你有
if (j == 0)
return 0;
内部computeOpt
.因此,您不能从一份工作中赚取任何收入。
在一般情况下,由于上面的行,您似乎忽略了第一份工作。 if (j < 0)
应该工作得更好。
PS 在您转到“10k 到 1m 随机生成的作业集” 之前,请始终测试简单和琐碎的案例。它们更易于验证和调试。
关于c - 加权区间调度问题和动态规划,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/3574986/