权区间调度问题及放大器;动态程序 [英] Weighted Interval Scheduling problem & Dynamic program
问题描述
我的问题是有关<一个href="http://stackoverflow.com/questions/3243234/algorithm-to-find-the-maximum-sum-in-a-sequence-of-overlapping-intervals">this其他讨论。
我试图用动态规划成一个递归调用来实现该算法。
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.
提出的书籍解决方案是使用一个溶液表来存储递归ö迭代呼叫期间需要时，将被重新使用所有suproblems
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.
要解决的问题的步骤是：
The steps to solve the problem are:
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]
}
这是我的code（相关部分）：
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＆LT; Ĵ这样的工作，我是其中j兼容。
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-计算-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\n", res);
我跑我的程序针对几个测试案例大数据（由1万1米随机生成的作业设置）我的输出比较预期的结果。在某些情况下，失败。有时我的输出为e位更高，有时又低于预期的结果有点小。我失去了出头明显。请注意，在大多数情况下我的输出是正确的，所以我认为有一些特别情况，我不能正确处理
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
我cant't找出问题所在。
I cant't find out where the problem is.
任何帮助是pciated AP $ P $
Any help is appreciated
更新： 我改变了递归函数成一个迭代，现在的结果是正确的所有测试文件。 再次，我不明白为什么递归人们不工作
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.
在一般的情况下，你似乎忽略了第一份工作，由于线之上。 如果（J＆LT; 0）。应该更好地工作。
In general case, you seem to ignore first job due to the line above. if (j < 0) should work better.
PS务必测试简单而琐碎的案件1万1米随机生成的作业设置的。它们更易于检验，更容易调试。
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屋！
