2

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

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

问题陈述：

工作 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 <= 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)：

#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 随机生成的作业集）的几个测试用例运行我的程序，将我的输出与预期结果进行比较。在某些情况下，它会失败。有时我的输出比预期的结果要大一些，有时比预期的结果要小一些。我显然错过了一些东西。请注意，在大多数情况下，我的输出是正确的，所以我认为有些特殊情况我无法正确处理

我找不到问题出在哪里。

任何帮助表示赞赏

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

4

1 回答 1

1

让我们考虑一个琐碎的案例，一份工作。你会打电话

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

那么，你有

    if (j == 0)
        return 0;

里面computeOpt。所以，你不能从一份工作中赚取任何东西。

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

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

于 2011-01-31T14:28:17.317 回答