動態編程間隔與工作

我試圖用編程動態規劃的時間間隔調度問題之間的時間安排。所有工作都有不同的（正面）權重，並且不重疊。這些權重表示不同的運行時間。作業之間可能存在三個「空白」的空閒時間。此外，每個作業的每個時間單位（以秒爲單位）需要一個資源。資源可以有不同的值。我想用動態編程算法（遞歸地）爲所有作業找到最小的資源總和。動態編程間隔與工作

可能更清楚一個例子：

比方說，你有三個就業機會，time units { 2, 2, 3 }，你有八個長{ 2, 5, 1, 8, 4, 1, 1, 5 }資源列表。招聘一個有兩個時間單位，因此兩種資源，而且因爲它是第一個作業將需要的資源列表的第2個資源。工作二不必在工作一開始後立即開始，它也可以從接下來的三個「間隙」中的一個開始。這第二份工作也需要兩項資源，並且因爲它可以從三項差距中的一項開始，而不是第一項工作，所以可能需要的資源是(1,8) (8,4) (4,1) (1,1) = 9 12 5 2（可用資源的不同總和）。所有工作的總和當然少於資源數量。

這繼續，直到所有作業完成。我想用動態編程算法（遞歸地）爲所有作業找到最小的資源總和。

我嘗試了不同的解決方法，但我覺得這是一個很難解決遞歸沒有任何其他功能。

我的確寫了下面的代碼，如我所料這是不這樣做的：

public static double getCost(int t, int q, int r, int[] jobs, double[] resources){ 
    double table[][] = new double[t+1][r+1]; 
    for(int i = 0;i < t;i++){ 
     for(int j = 0;j < r;j++){ 
      double cost = 0; 
      for(int k = j-jobs[i] + 1;k <= j;k++){ 
       if(k < 0){ 
        break; 
       } 
       cost = cost + resources[k]; 
      } 
      double min = Double.POSITIVE_INFINITY; 
      for(int l = 1;l <= q;l++){ 
       if(i == 0 && l == 1){ 
        min = cost+j-jobs[0]-l; 
       } 
       else{ 
        double neww = cost+j-jobs[i]-l; 
        if(neww < min){ 
         min = neww; 
        } 
       } 
      } 
      table[i+1][j+1] = min; 
     } 
    } 
    return table[t][r]; 
}

可有人請給我一些建議嗎？

來源

2012-12-21 n00b1990

首先，需要定義用於每個子問題的狀態下，所以：

sum[t][r] = Minimum cost using up to 't' indexes in 'timeUnits', 
      and 'r' indexes in 'resources' (exclusive indexes).

基礎案例是：

sum[0][0] = 0

然後更新基於先前值的數組值。有兩件事要計算：運行一項工作的成本，以及將它添加到什麼（間隙大小）。

For each t 
    For each r 
    cost = Sum(resources[i]) for i = r-timeUnits[t]+1 ... r 
    sum[t+1][r+1] = Min(cost + sum[t][r-timeUnits[t]-gap+1]) for gap = 0 ... 2 (0 only for t=0)

最終成本是使用所有時間單位的最小值。

編輯：我修改您的代碼，以便它通過你的測試用例。

int[] jobs = { 2, 2, 2 }; 
int[] resources = { 1, 2, 3, 4, 5, 6, 7, 8, 1, 1 }; 
int q = 2; 
int t = jobs.length; 
int r = resources.length; 

double table[][] = new double[t+1][r+1]; 

for(int i = 0;i <= t;i++){ 
    for(int j = 0;j <= r;j++){ 
     table[i][j] = Double.POSITIVE_INFINITY; 
    } 
} 
table[0][0] = 0; 

for(int i = 0;i < t;i++){ 
    for(int j = 0;j < r;j++){ 
     double cost = 0; 
     for(int k = j-jobs[i] + 1;k <= j;k++){ 
      if(k < 0){ 
       cost = Double.POSITIVE_INFINITY; 
       break; 
      } 
      cost = cost + resources[k]; 
     } 

     double min = Double.POSITIVE_INFINITY; 
     for(int l = 0;l <= q;l++) { 
      int index = j-jobs[i]-l+1; 
      if(index >= 0 && index <= r) { 
       min = Math.min(min, cost + table[i][index]); 
      } 
      if(i == 0) break; 
     } 

     table[i+1][j+1] = min; 
    } 
} 

double best = Double.POSITIVE_INFINITY; 
for(int x = 0; x < r; x++) { 
    best = Math.min(best, table[t][x+1]); 
} 

System.out.println("Best cost: " + best);

來源

2012-12-21 19:10:54 fgb

您好，感謝您的幫助。你提供的解決方案看起來像一個迭代的，這是沒有問題的。規則r-timeUnits [t] +1 ... r，這是什麼意思？類似於從i = r-timeUnits [t] +1到r的循環？其中r是資源中索引的數量？或者對於每個r？再次感謝您對我的讚賞。 – n00b1990

@ n00b1990您正在使用timeUnits [t]資源 - 從資源[r-timeUnits [t] +1]開始到資源[r]結束，因此請使用for-loop合計這些資源值。 – fgb

我確實使用了for循環，唯一的問題是當r是0時，它代表第一列。我會得到i = 0-timeUnits [t] + 1。如果timeUnits [t]> 1，我會因爲索引爲負而出現問題，至少這是我的？ – n00b1990

http://www.cse.psu.edu/~asmith/courses/cse565/F10/www/lec-notes/CSE565-F10-Lec-13-dyn-prog-intro.pptx.pdf

這會給明確解決問題的辦法

來源

2013-07-09 10:26:22 Shivendra

動態編程間隔與工作

回答

相關問題