我的问题与其他讨论有关 。
我正在尝试使用动态程序将该算法实现为递归调用。
问题陈述:
作业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("%ldn", res);
我针对几个具有大数据(从10k到1m随机生成的作业集)的测试用例运行我的程序,将我的输出与预期结果进行比较。 在某些情况下,它失败了。 有时我的输出有点大,有时比预期的结果要小一些。 我显然错过了一些事情。 请注意,在大多数情况下,我的输出是正确的,所以我认为有一些特殊条件我无法正确处理
我无法找出问题所在。
任何帮助表示赞赏
更新:我将递归函数更改为迭代函数,现在结果对于所有测试文件都是正确的。 再一次,我无法理解为什么递归的不起作用
让我们考虑一个简单的案例,一个工作。 你会打电话
long res = computeOpt(njobs-1); // computeOpt(0)
然后,你有
if (j == 0) return 0;
在computeOpt
里面。 所以,你不能从一份工作中获得任何收益。
在一般情况下,由于上面的行,您似乎忽略了第一份工作。 if (j < 0)
应该更好。
PS在进入“10k到1m随机生成的作业集”之前,始终测试简单和琐碎的案例。 它们更易于validation,更易于调试。
以上就是c/c++开发分享加权区间调度问题与动态程序相关内容,想了解更多C/C++开发(异常处理)及C/C++游戏开发关注计算机技术网(www.ctvol.com)!)。
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/562449.html