1

動的計画法を使用して間隔スケジューリングの問題をプログラムしようとしています。すべてのジョブには異なる (正の) 重みがあり、重複しません。これらの重みは、異なる実行時間を表します。ジョブ間に 3 つの「ギャップ」のアイドル時間が存在する場合があります。さらに、各ジョブの各時間単位 (秒単位) には 1 つのリソースが必要です。リソースはすべて異なる値を持つことができます。動的プログラミング アルゴリズム (再帰的) を使用して、すべてのジョブのリソースの最小合計を見つけたいと考えています。

例を使用すると、より明確になる場合があります。

3 つのジョブがtime units { 2, 2, 3 }あり、8 つの long のリソースのリストがあるとします{ 2, 5, 1, 8, 4, 1, 1, 5 }。ジョブ 1 は 2 つの時間単位を必要とし、したがって 2 つのリソースを使用します。これは最初のジョブであるため、リソース リストの最初の 2 つのリソースを使用します。ジョブ 2 は、ジョブ 1 の直後に開始する必要はありません。次の 3 つの「ギャップ」のいずれかから開始することもできます。この 2 番目のジョブも 2 つのリソースを必要とし、3 つのギャップのいずれかから開始でき、最初のジョブではないため、使用できるリソースの可能性は(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];
}

誰かアドバイスをください。

4

2 に答える 2

3

まず、各副問題の状態を定義する必要があります。

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

基本ケースは次のとおりです。

sum[0][0] = 0

次に、以前の値に基づいて配列の値を更新します。計算する項目は 2 つあります。ジョブを実行するコストと、それを何に追加するか (ギャップ サイズ) です。

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-21T19:10:54.360 に答える