加權區間調度問題和動態程序

Question

我的問題與this other discussion有關。

我想實現該算法使用動態程序進入遞歸調用。

問題陳述：

工作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隨機生成的作業設置）我的輸出比較預期結果。在某些情況下，它會失敗。有時候我的輸出比較大，有時候會比預期的結果稍差。我明顯錯過了一些東西。請注意，在大多數情況下我的輸出是正確的，所以我認爲有一些特殊情況我無法正確處理

我無法找出問題所在。

任何幫助表示讚賞

UPDATE： 我改變了遞歸函數到迭代之一，現在的結果是所有的測試文件正確。 再次我不明白爲什麼遞歸的不工作

Answer 1

讓我們考慮一個小事件，一份工作。你會打電話給

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

然後，你有

if (j == 0) 
     return 0; 

內computeOpt。所以，你無法從一份工作中賺取任何收入。

在一般情況下，由於上面的界限，您似乎忽略了第一份工作。 if (j < 0)應該更好。

PS在進入「10k至1m隨機生成的作業集」之前，請始終測試簡單和瑣碎的情況。它們更容易驗證並且更易於調試。