加权区间调度问题动态程序 [英] Weighted Interval Scheduling problem & Dynamic program
问题描述
我的问题与 这另一个讨论.
我正在尝试使用动态程序将该算法实现为递归调用.
I'm trying to implement that algorithm using the dynamic program into a recursive call.
问题陈述:
作业 j 开始于 sj，结束于 fj，并且具有权重或值 vj.
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.
解决问题的步骤是:
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):
全局变量:
typedef struct {
long start, stop, weight;
} job;
/* job array */
job *jobs;
/* solutions table */
long *solutions;
/* P(j) */
long *P;
-按完成时间对作业进行排序，以便 f1 > f2 >... > fn
-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);
计算 p(1), p(2), ..., p(n)其中 p(j) = 最大索引 i
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):
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
", res);
我针对具有大量数据(从 10k 到 1m 随机生成的作业集)的几个测试用例运行我的程序，将我的输出与预期结果进行比较.在某些情况下，它会失败.有时我的输出比预期的结果要大一些，有时比预期的结果要小一些.我显然错过了一些东西.请注意，在大多数情况下，我的输出是正确的，所以我认为有些特殊情况我无法正确处理
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.
感谢任何帮助
更新:我将递归函数更改为迭代函数，现在结果对于所有测试文件都是正确的.我还是不明白为什么递归的不起作用
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
推荐答案
让我们考虑一件小事，一份工作.你会打电话的
Let's consider trivial case, one job. You'll call
long res = computeOpt(njobs-1); // computeOpt(0)
那么，你有
if (j == 0)
return 0;
在 computeOpt 内.所以，你不能从一份工作中赚到任何东西.
inside computeOpt. So, you can't earn anything from one job.
在一般情况下，由于上面的行，您似乎忽略了第一份工作.if (j < 0) 应该会更好.
In general case, you seem to ignore first job due to the line above. if (j < 0) should work better.
PS 在您转到10k 到 1m 随机生成的作业集"之前，请始终测试简单和琐碎的案例.它们更容易验证和调试.
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.
这篇关于加权区间调度问题动态程序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
